First of all, what is “Vehicle Routing”? Vehicle Routing -VRP- is a common problem type in OR, which aims to provide service to demand points with a certain number of vehicles. VRP is introduced by Dantzig and Ramser (1959) -as Truck Dispatching Problem- and it is still a popular problem in OR studies. There are several variations of VRP, based on vehicle capacity, priority rule, time window, service type and more. Also, in real life, VRP needs to be solved in delivery of goods, waste collection, street cleaning, school bus routing and routing of salespeople. (Massimo Paolucci)
VRP is considered as a difficult problem due to size of feasibility set. It is proved to be NP-Complete (Lenstra and Rinnooy Kan, 1981). Without any restriction, suppose there are n demand points with one vehicle. Then total number of feasible solutions is simply n! which grows very fast. For n=5, # of solutions is 120 while for n=8, # of solutions is 40320 and for n=10 total number of possible routes is 3,628,200 (Check mjc2.com). As our brute-force attack (complete enumeration) fails, we need to solve problem with advanced OR methods. VRP is a combinatorial-integer optimization type of problem. (Wikipedia)
We defined the problem and its complexity, now, let’s have a look for the solvers for VRP.
In the February 2012 issue of OR/MS Today, a survey about Vehicle Routing Software is provided. They list 15 different commercial vehicle routing software. Years introduced of these software change from 1983 to 2011. This survey presents a comprehensive list of the VRP software until today. Although there are some free tools for VRP, complex problems with huge number of nodes/arcs need special equipment to be solved.
At first glance, “DISC” of MJC2 is dominant in terms of solution time. At page 4, it is stated that computation time for 50 routes, 1000 stops problem is typically takes a few seconds. DISC can be used on Windows, Linux, Unix systems and as a web service. However, price is provided with application and can be costly for small projects. In page 15, number of companies using DISC is stated between 100-500. Another VRP software, ArcLogistics of ESRI supports mobile devices and it has very cool features (flexibility, mobile-support, navigation and real-time vehicle tracking) . On top of solving VRP, such features could be useful for business world. Other than this list, I found a web application for routing, logvrp by Mert Torun.
By the way, we can talk about free solutions for academic research. I invite you to write any freeware/tool or software with academic license here to create a list of such useful tools. Let me begin with VRP Solver by Larry Snyder, which is free of charge for educational/research purposes.
Although there are improvements in computational technology, development in the solution techniques is still far away from industrial requirements. For those whom are interested, there is a comprehensive presentation about VRP in Practice by Geir Hasle.
Photo By PR®
Nice post!
Too often have I found myself having to build a VRP model from scratch, just to experiment with some meta-heuristics for a school paper. Academics/students with a background/interest in Mathematics/Operations Research without the skills/patience for die-hard coding (in C++/Java), have no choice but to spend their valuable time stuck in the debug/test/debug cycle.
So here’s an open-source VRP library with a Tabu Search framework: https://github.com/mck-/Open-VRP
With this framework, I hope to catalyze the research and application of routing solutions. Researchers in innovative new algorithms should not need to fiddle in the Eclipse debugger screen. They should be able to focus all their energy and effort in devising their heuristics. OR should be kept fun and engaging.
That’s why I wrote it in Lisp
(apologies for another Lisp call (in one of my previous comments), but for those reading this and wondering why I chose Lisp: http://kuomarc.wordpress.com/2012/03/05/the-uncommon-lisp-approach-to-operations-research/)
The ultimate vision for Open VRP is a simple intuitive toolkit for the OR community, free for anyone.
It’s Open Source, so any feedback is highly valuable!
Hi again Marc,
I can really understand what you mean. Same thing happens to me a few time for other type of OR problems. Once again, I determined to create a shortest path tool which I assume to work faster than available tools, in my sophomore. I spent almost two or three nights in front of Java debugger.
Your approach to Lisp and OR is really interesting indeed. I will check Open-VRP and share my comments here. Thanks for your interest.
Solving Vehicle Routing Problem « OR Complete | Collective Operations Research Blog http://t.co/v0AVltNn #orms #orblog #vrp via @orcomplete
Solving Vehicle Routing Problem « OR Complete | Collective Operations Research Blog http://t.co/6hhWVdRr
Here’s an another open source library for VRP: Drools Planner (java, Apache license), which you might want to take a look at:
http://www.jboss.org/drools/drools-planner
It has a vehicle routing problem (capacitated) with a visual GUI and is very flexible to add more constraints and/or data.
I am amazed. Drools Planner seems very capable for solving business problems. As I see, Drools use multiple algorithms for solving the problem. I also wonder how software performs for academic purposes.
Thanks for comment.
For academic purposes, the Drools Planner benchmarker is very valuable. It outputs a detailed report about all solvers configurations across all datasets. Take a look at an old example here: http://docs.jboss.org/drools/blog/2012-05-13/index.html
[…] now, let’s zoom in to the 20% with an example of one of my favourite puzzles in OR: Solving the Vehicle Routing Problem. Put simple, how do you minimize the total distance, while visiting all the clients within the time […]
Well: you VRP problems can now be very efficiently solved thanks to an easy-to-use, powerful, professional software: with http://www.routist.com your routes can be optimized with just a few clicks.
Try it for free on http://www.routist.com and tell us what you think.
Fabio
Nice overview!
And here is yet another java library solving rich vehicle routing problems. It is called jsprit and is hosted here: https://github.com/jsprit/jsprit. It is open source and comes with a LGPL license. It might be worth a trial :).