Solving Vehicle Routing Problem

Share

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®

Sertalp Bilal Çay

PhD Candidate and Teaching Assistant in Industrial and Systems Engineering Department at Lehigh University. Researcher on Conic Optimization, Inventory Theory, Supply Chain Management and Simulation. Blog: sertalpbilal.com