Description
The Single Vehicle Pickup and Delivery Problem with Time Windows (PDPTW)
This assignment is for groups of 3 students each (at most). If you want to do it alone you must get the permission of the instructor.
1. Goal
This programming project can be viewed as an application of searching algorithm in real world problems.
2. Specifications:
The single vehicle PDPTW deals with a number of customer requests that must be satisfied by one vehicle with a known capacity. The route of the vehicle usually starts and ends with a central depot. A request must be collected from a pickup location before being dropped off at a corresponding delivery location, and every pickup and delivery request is associated with a specific time window during which it must be served. If the vehicle arrives earlier than the beginning of the designated time window interval, it must wait until the service time begins. All requests must be served in a way that minimizes the total travel cost of the vehicle, without violating precedence, capacity and time windows constraints. One of the common approaches to solve this problem is using local searching, Genetic algorithms, and CSP. Therefore, the aim of this project is to use CSP approach to fine the routs that served requests in a way that minimizes the total travel cost of the vehicle, without violating precedence, capacity and time windows constraints. Please return to the following paper (specifically section 3: problem definition and 8.2: experiments and dataset) for more information about the problem.
https://users.cs.cf.ac.uk/C.L.Mumford/papers/M_Hosny.pdf
3. Submissions: Please submit the following: 1. Report:
• Describe in details your formalization of the problem.
- Write up to 10 pages to describe how you designed and implemented your program and list any assumptions you made for your project.
- Describe how to compile and run your program only when special directions are needed and unavoidable.
- In case you completed some extra credit items, you should describe how to enable and test them. Please, do not repeat in the report the text provided in this description.
2. Source Code : Include all the source code you developed or extended from the program. These need to be submitted only electronically (no hardcopies of the code). The running program needs also to be submitted electronically.
3. Demo: You will be asked to demo your work to your instructor. For that you need to be able to work with your program, introduce minor modifications and defend your choices.
