The problem

In this demo, we are solving multi-day vehicle routing problems. The task is to manage a fleet of trucks that need to visit customers over the course of several days. All trucks start at the same depot (marked in the middle as a black circle). Customers follow a certain visiting pattern, e.g. some customers need to be visited each day, while others require fewer visits.

Each customer has a fixed demand (e.g. the weight or size of the delivery), while each truck has a fixed capacity. The goal is to minimise the total travel distance, visiting all customers as required by their visiting patterns, and respecting the capacity constraints of the trucks.

Interactivity

Our experience is that many optimisation problems can only be solved satisfactorily if expert users are able to interact with the optimisation tools:

• When requirements change (e.g. a vehicle becomes unavailable), experts may need to explore different options and guide the tool towards a fix for the problem.
• Many problems have no clear definition of solution quality, e.g. when there are conflicting objectives (minimise the travel distance or the number of trucks?). Experts may want to explore, evaluate and combine different what-if scenarios to come up with an acceptable compromise.
• Some optimisation problems require human sign-off, in particular when important, far-reaching decisions have to be made (e.g. planning medical procedures or long-term strategic projects). It is important to provide interactive feedback and exploration of the solution space so that expert users can feel confident about the solution they are proposing to implement.

The interactive interface in this demo allows you to optimise individual days or individual routes in cooperation with our backend solving technology. You can also disable individual trucks on individual days and work together with the solver to come up with a new plan.

Our technology is not limited to solving Vehicle Routing Problems. We just chose this application because it demonstrates nicely what we are doing. The same ideas can be applied to other optimisation domains such as production scheduling, timetabling, or staff rostering problems.

Try it out!

To get started, load a scenario from the Load data menu. At any time, click the Help! button to find out about all the user interface elements.

Technology

The demo is based on technology developed at Monash University and NICTA/Data61.

The vehicle routing problem is modelled in MiniZinc, an expressive constraint modelling language. The model represents the requirements of vehicle routing in a high-level, easily maintainable way. It also expresses how the user can interact with the problem at the specification level, defining what it means to e.g. fix a day, update a single route, or disable a vehicle.

The MiniZinc model is executed using Gecode, an efficient, open-source solver based on Constraint Programming algorithms. The solver iteratively improves an existing solution by keeping parts of it fixed and searching through the remaining options (a technique called Large Neighbourhood Search).

The front-end is implemented in JavaScript and HTML, which is interacting through a WebSocket-based interface with a web service implemented in Haskell.

Contact

Guido Tack
Email: guido.tack@monash.edu
Phone: +61 (3) 9903 1214