VRP is a classic combinatorial optimization challenge and has been an active area of research for operations research gurus for 30+ years. Although a lot of research and progress has been made in academia, enterprises are far behind in using this technology effectively, primarily because of lack of integration with business friendly tools (a.k.a Excel).

Problem description: I need to solve a VRP-TW (VRP with Time Window) problem. I’ve a list of jobs that need to be serviced by a group of vehicles. The schedule created to service these jobs should minimize the total distance traveled by vehicles, with the following conditions:

Currently, such problems are solved in enterprises using commercial softwares like Matlab (sample code), iLog etc. But I’m wondering if there’s any solution available using R. 

3. There are many commercial package applications in this space, but I didn’t explore them. You can see the list of commercial VRP software here

4. R offers several optimization packages but I couldn’t find any to solve VRP

– TSP package helps with Traveling Salesman Problem but I’m not sure how to use it for multiple Travelling Salesmen Problem (mTSP), which is similar to VRP. TSP offers a simple API and hooks to several solvers including Concorde

– RSymphony package is a wrapper on COIN’s Symphony project (a solver for mixed integer linear programs) but lacks any useful documentation on solving mTSP or VRP problems using it

5. Mathematical modeling systems like AMPL, GAMS, AIMMS, ZIMPL offer solution to such problems. However, they seem unable to address large-scale problems (200+ jobs, 100+ vehicles). Checkout the complete list and a comparison on AIMMS website (caution: might be biased towards AIMMS)

– Zimpl is open source but can only solve small scale problems e.g. less than 19 vehicles! Here are some Zimpl examples. You can try TSP and Capacitated Facility Location Problem in Zimpl user guide

– My team mate had tried GAMS but found it lacking for large scale problems
– AMPL examples (TSP) seemed difficult to scale to mid-large scale problems. Their documentation and user interface wasn’t easy

– AIMMS looked interesting, It allowed me to access its complete functionality in its free trial download and offered several examples that looked promising (great user interface) – Gate assignment, Distribution center, Transport, Employee Scheduling, Travelling Salesman Problem. Here’s a AIMMS case study.

6. Some consumer apps like logVRP offer a great user interface but aren’t suitable for mid-large scale problems (100+ jobs, 50+ technicians).

7. More to follow…

---

LEARN MORE


Those interested in learning more about the Vehicle Routing Problem could read these articles
– VRP introduction part1, part2

and try out these examples:
– VRP windows executable
– Concorde TSP Solver
– Larry Snyder’s VRP solver
– logVRP site
– Routing Excel add-on

To leave a comment for the author, please follow the link and comment on their blog: Enterprise Software Doesn't Have to Suck.