The traveling salesman problem with time windows in postal services

Abstract

This article focuses on a variant of the travelling salesman problem with time windows (TSPTW) that arises in postal services and parcel deliveries. It differs from the classical TSPTW as follows. First, route duration is a significant concern, as human costs largely exceed vehicle costs, emphasising the importance of reducing waiting time. Second, customers are divided in two categories: Commercial ones with time windows and private customers without time window restrictions, making the NP-hard TSPTW even harder to solve. To support the first statement, we present a multi-objective approach based on a constraint programming formulation of the problem which allows to balance the optimisation of both human and material resources. To address the issue of large-scale sparsely time-constrained instances and reduce the size of the large real-world instances, we also introduce a cluster/solve/sequence approach that relies on a mathematical programming formulation to sequence the customer visits in the final step. This decomposition technique allows to produce high-quality solutions (with an average optimality gap of 1.31%) for industrial problems in less than one minute of computation time.

Keywords:

• Travelling salesman problem with Time windows
• postal services
• route duration
• bi-objective
• low time-window density
• clustering heuristic

Notes

Acknowledgements

We are thankful to the personnel of GIRO Inc., in particular, Charles Fleurent and Patrick Saint-Louis, who provided to us the problem definition and the real-life datasets.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 https://emplois.ca.indeed.com/cmp/Canada-Post/salaries.

2 http://www.ford.ca/commercial-trucks/transit-connect-cargo-van/2017/features/capability.

3 http://www2.nrcan.gc.ca/eneene/sources/pripri/price_map_e.cfm.

Additional information

Funding

We gratefully acknowledge the financial support of GIRO Inc., and the Natural Sciences and Engineering Research Council of Canada under the grant RDCPJ 4634633-14.