The traveling salesman problem with time windows in postal services

Alexis Bretin, Guy Desaulniers and Louis-Martin Rousseau

Journal of the Operational Research Society, 2021, vol. 72, issue 2, 383-397

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.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1678403 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:72:y:2021:i:2:p:383-397

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1678403

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().