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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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:

1. PWPInstanceReader

2. 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.

1. The number of locations can be calculated from the problem instance

2. 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

3. 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:

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of