Dynamic traveling salesman problem with stochastic release dates |
| |
| Institution: | 1. Department of Economics and Management, University of Brescia, C.da S. Chiara 50, Brescia, Italy;2. Ecole des Mines de Saint-Etienne and LIMOS UMR CNRS 6158, CMP Georges Charpak, Gardanne F-13541 France;1. HEC Liège, Management School of the University of Liège, Liège, Belgium;2. School of Business and Economics, Maastricht University, Maastricht, the Netherlands;1. Department of Economics and Business, University of Catania, Corso Italia, 55, 95129, Catania, Italy;2. Portsmouth Business School, Centre for Operational Research and Logistics (CORL), University of Portsmouth, Portsmouth, United Kingdom;1. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA;2. Department of Industrial Engineering and Management Systems, University of Central Florida, 12800 Pegasus Dr., Orlando, FL 32816, USA;3. Department of Industrial Engineering, University of Pittsburgh, 1048 Benedum Hall, Pittsburgh, PA 15261, USA;1. Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, Gent 9000 Belgium;2. Technology and Operations Management Area, Vlerick Business School, Belgium;3. UCL School of Management, University College, London, UK;1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, People’s Republic of China;2. Logistics Research Centre, Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong, People’s Republic of China |
| |
| Abstract: | The dynamic traveling salesman problem with stochastic release dates (DTSP-srd) is a problem in which a supplier has to deliver parcels to its customers. These parcels are delivered to its depot while the distribution is taking place. The arrival time of a parcel to the depot is called its release date. In the DTSP-srd, release dates are stochastic and dynamically updated as the distribution takes place. The objective of the problem is the minimization of the total time needed to serve all customers, given by the sum of the traveling time and the waiting time at the depot. The problem is represented as a Markov Decision Process and is solved through a reoptimization approach. Two models are proposed for the problem to be solved at each stage. The first model is stochastic and exploits the entire probabilistic information available for the release dates. The second model is deterministic and uses an estimation of the release dates. An instance generation procedure is proposed to simulate the evolution of the information to perform computational tests. The results show that a more frequent reoptimization provides better results across all tested instances and that the stochastic model performs better than the deterministic model. The main drawback of the stochastic model lies in the computational time required to evaluate a solution, which makes an iteration of the heuristic substantially more time-consuming than in the case where the deterministic model is used. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
