Scientific Program > Talks by Speaker > Meyer Anne

A Hybrid Approach for the Travelling Salesman Problem with General Time Windows
Anne Meyer  1, *@  , Katharina Glock  1, *@  , Felix Brandt  1, *@  , Björn Regenhardt  2, *@  
1 : FZI Research Center for Information Technology  (FZI)  -  Website
Haid-und-Neu-Straße 10-14 76131 Karlsruhe -  Germany
2 : PTV Group
Haid-und-Neu-Straße 15 76131 Karlsruhe -  Germany
* : Corresponding author

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).

Online user: 2 RSS Feed