VRP Algorithms - pgRouting/pgrouting GitHub Wiki

List of VRP algorithms with basic information, links, etc. All of these problems are NP-hard and exact solutions are not worth the effort to implement. They are only interesting from an academic point of view. In the real world there are many iterative solutions the give good results in reasonable run-times. Our current TSP solution uses simulated annealing, our single depot with time windows uses a TABU search. If you are interested in working on these I strongly recommend that you read up on TABU search and plan to implement it using a TABU search algorithm. We are open to others solvers but I would be good to discuss that on the dev list and explain the benefits of another algorithm so we can all learn from the discussion.

Links

• http://wiki4city.ieis.tue.nl/index.php?title=VRP An excellect overview.

• http://wiki4city.ieis.tue.nl/index.php?title=VRPTW

• http://wiki4city.ieis.tue.nl/index.php?title=VRPPD

• http://wiki4city.ieis.tue.nl/index.php?title=VRPSPD

• http://neo.lcc.uma.es/vrp/ Good description of various VRP problems and how to solve them. Also has some benchmark data for testing.

• http://www.verolog.eu/ VeRoLog is the Working Group on Vehicle Routing and Logistics Optimization within EURO, the Association of the European Operational Research Societies.

• https://code.google.com/p/or-tools/ Operations Research Tools developed at Google

• RinSim is a multi-agent system simulator written in Java. It supports problems in the fields of transportation and logistics, most notably pickup-and-delivery problems (PDP).

• Multi-agent Pickup and Delivery Planning with Transfers

• https://github.com/jsprit/jsprit

Test Cases

• http://dev.heuristiclab.com/trac/hl/core/wiki/Vehicle%20Routing%20Problem
• http://www.sintef.no/Projectweb/TOP/PDPTW/Li--Lim-benchmark/ (VRPDPTW cases)
• http://neumann.hec.ca/chairedistributique/data/ Various test cases and results.

TABU Search

One of the key optimiation algorithms used for solving VRP problems is based on the Tabu Search Algorithm. This was developed by Fred Glover and here are some critical papers that you will find referenced in most all VRP papers that use Tabu Search:

• Tabu Search - Part I
• Tabu Search - Part II
• Tabu Search: A Tutorial
• Fred Glover's Home Page

Papers

Here are a collection of links to papers that I found interesting. There are tons of papers on the web just google for the terms you are interested in:

• Three Strategies Tabu Search for Vehicle Routing Problem with Time Windows
• Pickup and Delivery with Time Windows : Algorithms and Test Case Generation
• Overview of VRP Types and Algorithms
• Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery
• Large neighborhood search
• An Adaptive Large Neighborhood Search Heuristic for the Cumulative Capacitated Vehicle Routing Problem
• An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows
• Heuristics for Service Technician Routing and Scheduling Problems
• An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops
• Heuristic Techniques for Solving the Vehicle Routing Problem with Time Windows
• A Classification Scheme for Vehicle Routing and Scheduling Problems
• Towards a model and algorithm management system for vehicle routing and scheduling problems
• A Library of Vehicle Routing Problems
• A Fast Tabu Search Implementation for Large Asymmetric Traveling Salesman Problems Defined on Sparse Graphs
• Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey
• A Tabu Search Heuristic for the Generalized Traveling Salesman Problem
• Pickup and Delivery with Time Windows : Algorithms and Test Case Generation
• Vehicle Routing in Practice
• Pickup and Delivery Problem with Time Windows: A Survey
• Benchmark Test Cases for VRPTW and PDPTW
• Benchmark Test Cases for VRPTW
• Using Column Generation for the Pickup and Delivery Problem with Disturbances
• Models and Algorithms for the Heterogeneous Dial-a-Ride Problem with Driver Related Constraints
• A Tabu Search Heuristic for the Vehicle Routing Problem
• A Survey on the Vehicle Routing Problem and Its Variants
• A general heuristic for vehicle routing problems
• Survey and Overview of VRP
• Class Note/Lecture on VRP
• Rich Vehicle Routing Problems and Applications, Min Wen, PhD Thesis
• A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows
• A CENTROID-BASED HEURISTIC ALGORITHM FOR THE CAPACITATED VEHICLE ROUTING PROBLEM

TABU search related :

https://class.coursera.org/optimization-002/lecture/57 @12:48

https://class.coursera.org/optimization-002/lecture/59

TSP - Traveling Salesman Problem

• [...]

DARP - Dial A Ride Problem

Also see VRPPD below.

• [...]

VRP - Vehicle Routing Problem

• [...]

VRPH - Vehicle Routing Problem with Heuristic

• [...]

CVRP - Capacitated Vehicle Routing Problem

• [...]

VRPTW - Vehicle Routing Problem with Time Windows

• [...]

CVRPTW - Capacitated Vehicle Routing Problem with Time Windows

• [...]

VRPPD - Vehicle Routing Problem, Pickup and Delivery

Also see [VRP Pickup Delivery Problem](VRP Pickup Delivery Problem)

• http://www.dim.uchile.cl/~tcapelle/TESIS/NanryPDPTW.pdf
• http://www.diku.dk/~sropke/Papers/Branch-and-Cut-and-Price%20for%20the%20Pickup%20and%20Delivery%20Problem%20with%20Time%20Windows.pdf
• http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2266430 Check this :VRP-SDP