This paper focuses on the traveling salesman problem with time windows (TSPTW) that arises in postal services and parcel deliveries and has features differing from the classical TSPTW. First, route duration is a significant concern, as human costs largely exceed vehicle costs, emphasizing the importance of reducing waiting time. Second, if commercial customers usually have a time window, private customers do not, making the NP-hard TSPTW even harder to solve. To address these issues, we present two multi-objective approaches based on a constraint programming formulation of the problem which allows to balance the optimization of both human and material resources. We also introduce a cluster/solve/sequence approach to reduce the size of the large real-world instances, which relies on a mathematical programming formulation to sequence the customer visits in the final step. This decomposition technique allows to produce high-quality solutions for industrial problems in about a minute of computation time.
Published April 2018 , 21 pages