Scientific Program > Talks by Speaker > Meyer Anne

In urban distribution of supplies to restaurants, short travel and service times as well as low delivery volumes enable logistics providers to serve a large number of customers per day. We consider an application where a driver is responsible for an area of customers for which no feasible route might exist if hard time windows were enforced. Instead, restaurants specify delivery time preferences, taking into account their opening hours and their rush hours during which service is not desirable. This is a special case of the Vehicle Routing Problem with General Time Window, which we define as the Travelling Salesman Problem with General Time Windows (TSP-GTW).

In a TSP-GTW, we model preferences as piecewise linear penalty functions, which may comprise multiple preferred intervals, penalties for early or late delivery and intervals where service is forbidden. The objective in our case is to find a tour that minimizes in a hierarchical order (a) total penalty cost, (b) number of customers with nonzero service penalty, and (c) total route duration.

We present a solution approach for the TSP-GTW combining a Constraint Programming model, a regret based route construction heuristic and a dynamic programming approach for determining minimum service cost. In order to minimize route duration, we iteratively enhance this approach with customer sequences from solving the TSP-TW with artificially increased zero penalty time slots using dedicated TSP-TW approaches. We successfully evaluated this hybrid heuristic on artificial and on real-world instances from a food distributor in Paris (France).