Nov 9, 2010

Any R packages to solve Vehicle Routing Problem?

Are there any R packages to solve Vehicle Routing Problem (VRP)?

I looked around but could not find any... Any leads?

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:
- Customer SLA (time window promised to customer) should be met
- The parts in the vehicle should match what the job requires

I have the following information available about the jobs and vehicles
- Job ID, Job address, Job duration, Job priority, Earliest start time, Latest finish time, Date, Parts required
- Vehicle ID, Base location (address), Start time, End time, Parts

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. 


Disclaimer: I'm completely new to Operations Research, so this might be amateurish

1. I found open source implementations in C, C++ and Java on COmputational INfrastructure forOperations Research website.

2. Commercial solvers like Concorde seem to get great reviews in solving Traveling Salesman Problem (TSP)

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 AMPLGAMS, 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...


Those interested in learning more about the Vehicle Routing Problem could read these articles
- VRP introduction part1part2
- Dynamic VRP
- Research on Multiple TSP: Article 1, Article 2
- Test your program with standard VRP problemsTSP problems
- VRP Web

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


  1. Have you tried the TSP package?

  2. Hi Rob, yes, I looked at TSP but could not figure out how to solve Vehicle Routing Problem, which is similar to multiple Travelling Salesmen Problem. Have you come across any useful examples to solve VRP or mTSP using TSP package?

    PS: I've updated my research notes in the post

  3. Here is a TSP library of problem instances and examples

  4. Rsymphony: Symphony in R
    An R interface to the SYMPHONY MILP solver form COIN-OR.

    But you should know how to formulate problem.

  5. Hello,
    I'm also working on solving CVRP and I came across VRPH Library, which I was able to compile and test for medium sized instances (e.g. 50jobs, 10 vehicles) but I suppose it might work for larger ones too.

    I know it's been a while but in the end, which solution did you go with?



  7. sebastian, I investigated several libraries to solve VRP and decided to build a custom desktop application using open source libraries from COIN-OR. I've attached screenshots in this post

  8. If you adhere to those recommendations, Salesperson Jobs you can hire a organization where you can create 10 times the benefit with the same attempt and work that someone will create in a revenue job in business The united states. Let me give you an example.

  9. This is such a great blog. you really covered it all. Thank you for sharing such an important information. Hope to get some more information in future also.
    Husband Wife Dispute Specialist
    Career or job Problem Specialist
    Love Vashikaran Specialist in India.
    100% satisfaction guarantee Call @ +91-9815872813.

    Shri Mukesh Aghori Ji

  10. Vehicle routing programming works. However notwithstanding numerous fruitful executions of this innovation, there are activities that did not satisfy desires. There is no enchantment recipe yet by taking after these seven stages you can guarantee that your vehicle routing project is effective.

  11. Subsequent to being utilized only for military purposes, worldwide situating frameworks (GPS) are currently accessible for common use. GPS innovation has turned into a piece of today's life so it is not viewed as some sort of a supernatural occurrence any all the more, yet rather as a helpful instrument for route in obscure places and getting from point A to point B with less agony.

  12. I have been through several posts on this very subject but the satisfactory information that I found here is something that all other blogs are missing.
    cash for cars sydney