This paper studies a generalization of the shortest path tour problem with time windows (GSPTPTW). The aim is to find a single-origin single-destination shortest path, which has to pass through an ordered sequence of not necessarily disjoint node-subsets. Each node has a time window for each node-subset to which it belongs. We investigate the theoretical properties of GSPTPTW and propose a dynamic programming approach to solve it. Numerical results collected on a large set of new benchmark instances highlight the effectiveness of the proposed solution approach.
A generalized shortest path tour problem with time windows / Di Puglia Pugliese, L.; Ferone, D.; Festa, P.; Guerriero, F.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 83:2(2022), pp. 593-614. [10.1007/s10589-022-00405-8]
A generalized shortest path tour problem with time windows
Ferone D.;Festa P.
;
2022
Abstract
This paper studies a generalization of the shortest path tour problem with time windows (GSPTPTW). The aim is to find a single-origin single-destination shortest path, which has to pass through an ordered sequence of not necessarily disjoint node-subsets. Each node has a time window for each node-subset to which it belongs. We investigate the theoretical properties of GSPTPTW and propose a dynamic programming approach to solve it. Numerical results collected on a large set of new benchmark instances highlight the effectiveness of the proposed solution approach.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.