VRP Algorithms

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.

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:

• 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

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