The probabilistic pickup-and-delivery travelling salesman problem
| Autor: | Mercedes Landete, Juan-José Salazar-González, Enrique Benavent, Gregorio Tirado |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Heuristic Heuristic (computer science) Computer science General Engineering Probabilistic logic 02 engineering and technology Travelling salesman problem Computer Science Applications 020901 industrial engineering & automation Artificial Intelligence 0202 electrical engineering electronic engineering information engineering Probability distribution 020201 artificial intelligence & image processing Pickup Routing (electronic design automation) |
| Zdroj: | Expert Systems with Applications. 121:313-323 |
| ISSN: | 0957-4174 |
| DOI: | 10.1016/j.eswa.2018.12.028 |
| Popis: | Transportation problems are essential in commercial logistics and have been widely studied in the literature during the last decades. Many of them consist in designing routes for vehicles to move commodities between locations. This article approaches a pickup-and-delivery single-vehicle routing problem where there is susceptibility to uncertainty in customer requests. The probability distributions of the requests are assumed to be known, and the objective is to design an a priori route with minimum expected length. The problem has already been approached in the literature, but through a heuristic method. This article proposes the first exact approach to the problem. Two mathematical formulations are proposed: one is a compact model (i.e. defined by a polynomial number of variables and constraints); the other one contains an exponential number of inequalities and is solved within a branch-and-cut framework. Computational results show the upsides as well as the breakdowns of both formulations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect