jeudi 18 novembre 2010

Vehicle Routing Library

Vincent Furnon, who moved from ILOG to Google, has just released a vehicle routing library.
This means that you can really save money by using some products instead some others. In addition, some nice and clever people will be very happy to help you to develop your application whereas some others will see more and more the life in dark blue.

Here is his presentation about his new development. I really encourage you to test it.

"We just pushed the vehicle routing extension of the CP Solver. It's a 
layer above the CP Solver which lets you model a wide range of vehicle 
routing problems from the Traveling Salesman Problem (and its 
variants, ATSP, TSPTW, ...) to multi-vehicle problems with dimension 
constraints (capacities, time windows) and various "routing" 
constraints (optional nodes, alternate nodes,...). Given it exposes 
the CP variables one can extend the model using the constraints 
available in the CP Solver. 

Concerning the resolution of the problem, most of the "cabling" is
hidden so you just need to call the Solve() method on the RoutingModel
class. However the search can be parametrized using command-line
flags. We are mainly using CP-based local search and large
neighborhood search using routing-specific neighborhoods.
Implementations of Tabu Search and Guided Local Search are available
too and have proven to give good results (especially GLS). 
The basic library is in C++ and a Python-wrapped version is available
Documentation will be added in the future but you can have a look at
the TSP example (both in C++ and Python) as a starting point. We'll be
adding a CVRPTW example very shortly. "

3 commentaires:

  1. It sounds great!
    Where is it actually?

  2. And ou et Vincent Furnon? I have a question for him, as one runner to another. Paul Melzer