Program > By speaker > Bretin Alexis

Parcel delivery is becoming an important activity of the postal services. The customers are divided into disjoint territories and one route must be established for each territory. Typically, around 10% of the customers (mostly commercial ones) must be serviced within relatively tight time windows. The others can be serviced at any time. In this context, the problem of building a route for a territory corresponds to a traveling salesman problem with time windows (TSPTW). This problem has recently been formulated using time buckets. However, for instances with 100 to 200 customers and no time windows for most of them, the time-bucket model becomes intractable. In this talk, we propose a heuristic approach that starts by clustering the customers to obtain a reduced-sized problem, then solves the corresponding time-bucket model, before desaggregating the clusters to obtain a final solution. We consider different clustering and desaggregation procedures and present various computational results to compare their effectiveness.