Important Notes on my Project

Basic plan to proceed

• Generate Initial Solution

  • Reference: Construction of initial solution

  • Based on two algorithms:

    • Sequential Construction
    • Hill Climbing Method. (Also called as Neighborhood Move)

• Optimize the initial solution using TABU.

  • Reference1: Reactive TABU Search
  • Reference2: Steve's Notes on TABU

Work done till now :

* Completed the first part of the problem i.e.., Getting the initial solution.
* You can find the code here [Code for initial solution](https://github.com/pgRouting/pgrouting/blob/gsoc-vrppdtw/src/vrppdtw/src/pdp.cpp)
* The header file contains all the data structures required to solve the problem. 

Work to be done :

* To complete the second part i.e.. TABU search
* Integrate into pgRouting.

Conclusions:

The experimental results on a large number of benchmark instances indicate that the sequential construction heuristic (SEQ) seems to be the most favourable solution construction method, which can be by easily embedded in a heuristic or a meta-heuristic technique to reach final good quality solutions. With just a few simple lines of code, and without a pre-determined number of vehicles or a solution evaluation mechanism, this algorithm produced good quality results, that are sometimes even better than the results obtained by the most sophisticated parallel algorithm tested in our research (the PBQ algorithm)

Practical Applications of VRP-PDP:

• Transportation of raw materials from suppliers to factories.
• Internet-based pickup from sellers and delivery to buyers
• Pickup and delivery of charitable donations from homes to different organizations
• Transport of medical samples from medical offices to laboratories