A progressive hedging method for the multi-path travelling salesman problem with stochastic travel times
| Autor: | Francesca Maggioni, Guido Perboli, Luca Gobbato |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Economics Computer science Heuristic (computer science) Strategy and Management 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Travelling salesman problem Econometrics and Finance (all)2001 Economics Tourism Management Information Systems Set (abstract data type) stochastic programming progressive hedging 0502 economics and business Multiple paths Progressive hedging Stochastic programming Stochastic travel times TSP Modeling and Simulation Economics Econometrics and Finance (all)2001 Economics Econometrics and Finance (miscellaneous) 1409 Tourism Leisure and Hospitality Management Applied Mathematics 050210 logistics & transportation 021103 operations research Leisure and Hospitality Management 05 social sciences multiple paths Solver stochastic travel times Econometrics and Finance (miscellaneous) Path (graph theory) Benchmark (computing) Settore MAT/09 - Ricerca Operativa General Economics Econometrics and Finance Wireless sensor network |
| Zdroj: | Politecnico di Torino-IRIS |
| Popis: | In this paper, we consider a recently introduced problem specifically designed for Smart Cities and City Logistics applications: the multi-path travelling salesman problem with stochastic travel costs (mpTSPs)(mpTSPs). The mpTSPsmpTSPs is a variant of the TSP problem where a set of paths exists between any two nodes and each path is characterized by a random travel time. We propose a two-stage stochastic programming formulation where tour design makes up the first stage, while recourse decisions related to the choice of the path to follow are made in the second stage. To solve this formulation, we propose a heuristic method inspired by the Progressive Hedging (PH) algorithm of Rockafellar & Wets (1991, Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res., 16, 119–147.) We then benchmark the solution method by solving model instances derived from the traffic speed sensor network of the city of Turin. Furthermore, the impact of the stochastic travel time costs on the problem solution is examined, showing the benefits of the proposed methodology in both solution quality and computational effort when compared to solving the deterministic equivalent formulation using a commercial solver. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|