AIM Project 2020 – Implementation of a HyFlex Compatible Postal Worker Problem (PWP) Domain
1 INTRODUCTION
The Postal Worker Problem (PWP) is a routing-type problem which states that given N number of postal deliveries, a post office depot, and the postal workers home address, the objective is to find a route which ensures that all postal deliveries are made exactly once such that the total tour length is minimised whereby the postal worker starts their shift at the start of the day at the post office depot, and finishes their day by returning to their home address once all deliveries have been made.
HyFlex is a software framework designed for the implementation and testing of iterative general- purpose search methods and will be/was covered in the “HyFlex Tutorial Lab” (13/03/2020).
2 OBJECTIVES
The aim of this project is to implement a HyFlex compatible PWP problem domain. A template code base is given to you to give you a starting point. You may wish to add more classes in your implementation; this is fine if each of the supplied classes and methods function as described in their requirements. There are several components which you must implement, some of which can be accomplished multiple ways with the hardest attracting more marks as detailed in each section. These will be highlighted in this document in green to highlight these areas. Below you will find a breakdown of each of these components along with a description of what you are expected to implement.
3 DEADLINE AND MARKS
You should submit a single zip folder containing all your source files, any libraries used, and the instance files – that is, so that we can run it without any compilation errors caused by missing files!
This project consists of an implementation, and a 2,000-word report with a maximum 4-page limit (using 11pt font!). The weightings for each are 80% implementation and 20% report.
PWP DOMAIN COMPONENTS
PROBLEM REPRESENTATION
You are to use a permutation representation using an array of integers (int[]) for representing solutions to the PWP problem instances such that each integer corresponds to an individual postal delivery whose mapping is specified by the order each delivery address appears in the instance file(s).
INSTANCE READER
Problem instances are stored as *.pwp files and reside in the folder “instances/pwp/*.pwp”. To be able to “load” an instance using HyFlex’s problem.loadInstance(int id) method, you should fulfil two components:
PWPInstanceReader
loadInstance(int id)
PWPInstanceReader
You should implement the readPWPInstance method in the PWPInstanceReader class to read in an instance from a given file, returning a new PWPInstance Object. Each PWP instance file is a plain text written in accordance to the following structure where the structure is in bold, and data italic:
The readPWPInstance method should return an instance of a PWPInstance Object which contains all the information relating to the problem instance. Moreover, it contains a factory method to create solutions to the current problem instance given an InitialisationMode. As discussed in Section 4.3, you only need to implement random initialisation.
To create a PWPInstance, five components are required: the t otal number of locations, an array of Locations, the Location of the post office depot, the Location of the worker’s home address, and a seeded random number generator.
The number of locations can be calculated from the problem instance
Each Location object is essentially a wrapper for an x and y coordinate and should be populated depending on the information from the problem instance file specified by the Path supplied to the readPWPInstance
The random number generator is passed as an argument to the readPWPInstance
loadInstance(int id)
This method should map instance IDs as integers to each of the problem instances stored in the “instances/pwp/*.pwp” folder. Once the respective instance is located, it should use the PWPInstanceReader class to load the instance information as a PWPInstance Object.
At this point, it is a good idea to set the objective function to be used by each of the heuristics.
SOLUTION INITIALISATION
The order of postal delivery addresses should be chosen at random (dependent on a seeded random number generator).
OBJECTIVE FUNCTION
To evaluate the cost of a solution, you should calculate the total distance of the postal workers journey starting at the postal depot and ending at their home. Distances between two locations should be calculated as their Euclidean distance. That is, in the below example, the total distance should be calculated using both sets of green and yellow routes.
Figure 1 - Sample solution illustrating the postal worker's delivery route and return journey.
Standard Evaluation
This is the easiest evaluator to implement. A standard evaluator takes the current solution and calculates the sum of distances between each location, setting the objective function value of the solution once the entire calculation is complete using the method below.
PWPSolution.setObjectiveFunctionValue(double objectiveFunctionValue);
4.4.1 Delta Evaluation
This is more complicated than the standard evaluation technique but is much faster and will attract more marks (if implemented correctly!). Delta evaluation exploits the fact that if a segment of a route is not changed, then neither will the distance of that route segment. Hence, only the path between locations that are removed and created need to be calculated. Beware of the trips between the postal office and worker’s home locations with the start and end points of the explicitly represented route!
Each time a heuristic is applied to a solution, its objective value must be updated during the application of the heuristic. By subtracting the removed part(s) of the tour from the current objective function value, and adding back the newly created part(s) of the tour using the methods:
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
