Program > Brainstorming sessions

When is a route really feasible in practice? Bas den Heijer and Gerhard Post - ORTEC Monday, June 6 - 2:00pm Room: Charpak

Optimizing the order of stops in a vehicle route can be challenging enough assuming an easy check for the feasibility of a given route. However in practice, the conditions that customers and legislation can impose on a route are diverse and mostly very tricky. The basic scientific conditions: time windows for tasks (1), total capacity of the truck (2), and maximum duration of the route (3) all have variants that are highly non-trivial: 1. Consider the best known solutions of the 300 VRPTW benchmarks by Gehring and Homberger. Very small increases of the travel time estimates render all 300 solutions infeasible. Hence a customer requesting robust routes will find these solutions unacceptable. 2. Instead of 1-dimensional loading, the vehicle can have compartments or the loading itself can be a 3-dimensional packing problem. 3. Rules of driving hours, breaks, and rest give additional restrictions on a route, which can depend on the driver driving it. How to incorporate these conditions while running a routing algorithm is not obvious. We invite the audience to express their opinions on these.

The VRP with Rhythms Tore Grünert - GTS Systems and Consulting Tuesday, June 7 – 2:00pm Room: Charpak

In this workshop I would like to present and discuss an interesting variant of the vehicle routing problem (VRP) that is often encountered in practice. In the VRP with rhythms (VRPR), we are given a number of periods and a number of orders. Each order has a rhythm that specifies the number of periods between two visits. For example, if the rhythm is one, the order has to be executed every period, if it is two, it has to be executed every other period etc. If we take all rhythms into account, the least common multiple (lcm) of all rhythms determines the planning horizon, i.e. the time after which the execution of the orders will repeat. For example, if we have orders with rhythms 1, 2, 3 and 4, the lcm is 12, meaning that any rhythmic pattern will repeat after 12 periods. For each order the decision maker can decide about the starting period of the order. For example, if the order has a rhythm of 4 and the starting period is 3, the active periods are 3, 7, 11 etc. Using these starting periods, the active orders are known for each period of the planning horizon. 

The task of the VRPR is thus to allocate each order to one route, choose a starting period for the order and to sequence the orders within a ‘master’ route so that the routes that contain the active orders of the period are feasible and cost-optimal over the entire planning horizon. Depending on the application context, the routes usually have to fulfil typical constraints of a VRP, like time windows and capacity constraints. In addition, it is usually required that the workload (capacity utilisation, distance, total route duration) is balanced over the periods. 

Very often, the orders have a probability in addition to a rhythm. This means that the customer decides shortly before execution whether the order needs to be executed or not. Note that the VRPR assumes that the allocation to the vehicle and the sequence of the orders in the master route is fixed. 

The VRP with rhythms occurs regularly in the waste industry, where different types of waste have different rhythms. Another application area is the planning of service or sales staff. Here, different types of customers may have different service or visitation intervals.