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

• About TABU :

  • TABU1
  • TABU2

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
• The header file contains all the data structures required to solve the problem.
• To complete the second part i.e.. TABU search
• Integrate into pgRouting. (Partial Optimization is done)

Work done to be done :

• Try to implement a few more and get better optimized results

What I learnt :

• Read different heuristics which are important for NP-hard problems.
• I was trying to implement everything in Object Oriented Programming. This is the first time I'm coding in oop, I'm learning many things regarding that. Any suggestions are welcome.
• Trying to solve some errors using GDB. Steve helped me a lot in understanding it.
• Integrating into pgRouting is not that much easy thing to do, need to understand the backend pgsql magic and debug a lot ;)

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