New Neighborhood Structures For The Double Traveling Salesman Problem With Multiple Stacks
| dc.contributor.author | Felipe Ortega, Ángel | |
| dc.contributor.author | Ortuño Sánchez, María Teresa | |
| dc.contributor.author | Tirado Domínguez, Gregorio | |
| dc.date.accessioned | 2023-06-20T09:33:18Z | |
| dc.date.available | 2023-06-20T09:33:18Z | |
| dc.date.issued | 2009 | |
| dc.description | International Workshop On Operational Research Conference Held In Honor Of Laureano F Escudero,Jun 05-07, 2008,Madrid | en |
| dc.description.abstract | Abstract The changing requirements in transportation and logistics have recently induced the appearance of new vehicle routing problems that include complex constraints as precedence or loading constraints. One of these problems that have appeared during the last few years is the Double Traveling Salesman Problem with. Multiple Stacks (DTSPMS), a vehicle routing problem in which some pickups and deliveries must be performed in two independent networks, verifying some precedence and loading constraints imposed on the vehicle. In this paper, four new neighborhood structures for the DTSPMS based on reinsertion and permutation of orders to modify both the routes and the loading planning of the solutions are introduced and described in detail. They can be used in combination with any metaheuristic using local search as a subprocedure, guiding the search to unexplored zones of the solution space. Some computational results obtained using all proposed neighborhood structures are presented, providing good quality solutions for real sized instances. | en |
| dc.description.department | Depto. de Estadística e Investigación Operativa | |
| dc.description.faculty | Fac. de Ciencias Matemáticas | |
| dc.description.refereed | TRUE | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/15083 | |
| dc.identifier.citation | Felipe, A., M. T. Ortuño, y G. Tirado. «New Neighborhood Structures for the Double Traveling Salesman Problem with Multiple Stacks». TOP 17, n.o 1 (julio de 2009): 190-213. https://doi.org/10.1007/s11750-009-0080-9. | |
| dc.identifier.doi | 10.1007/s11750-009-0080-9 | |
| dc.identifier.issn | 1134-5764 | |
| dc.identifier.officialurl | https//doi.org/10.1007/s11750-009-0080-9 | |
| dc.identifier.relatedurl | http://www.springerlink.com/content/n165424710362747/fulltext.pdf | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/49890 | |
| dc.issue.number | 1 | |
| dc.journal.title | Top | |
| dc.language.iso | eng | |
| dc.page.final | 213 | |
| dc.page.initial | 190 | |
| dc.publisher | Springer | |
| dc.rights.accessRights | restricted access | |
| dc.subject.cdu | 517.986 | |
| dc.subject.keyword | Traveling Salesman Problem | |
| dc.subject.keyword | Metaheuristics | |
| dc.subject.keyword | Neighborhood Structures | |
| dc.subject.keyword | Precedence Constraints | |
| dc.subject.keyword | Lifo Loading | |
| dc.subject.ucm | Ecuaciones diferenciales | |
| dc.subject.unesco | 1202.07 Ecuaciones en Diferencias | |
| dc.title | New Neighborhood Structures For The Double Traveling Salesman Problem With Multiple Stacks | en |
| dc.type | journal article | |
| dc.volume.number | 17 | |
| dcterms.references | Carrabs F, Cordeau J-F, Laporte G (2007) Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS J Comput 19:618–632 Cassani L, Righini G (2004) Heuristic algorithms for the tsp with rear-loading. In: 35th annual conference of the Italian Operational Research Society, AIRO XXXV, Lecce, Italy Clarke G, Wright J (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581 Cordeau J-F, Laporte G, Potvin J-Y, Savelsvergh MW (2006) Transportation on demand. In: Barnhart C, Laporte G (eds) Transportation. Handbooks in operations research and management science, vol 14.Elsevier, Amsterdam. Cordeau J-F, Iori M, Laporte G, Salazar-González J (2009). A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks (to appear) Desaulniers G, Desrosiers J, Erdmann A, Solomon MM, Soumis F (2002) VRP with pickup and delivery. In: Toth P, Vigo D (eds) The vehicle routing problem. SIAM, Philadelphia, pp 225–242. Chap 9 Doerner DF, Fuellerer G, Hartl RF, Gronalt M, Iori M (2007) Metaheuristics for the vehicle routing problem with loading constraints. Networks 49(4):294–307 Glover F, Laguna M (1997) Tabu search. Kluwer, Norwell Gendreau M, Iori M, Laporte G, Martello S (2006). A heuristic algorithm for a routing and container loading problem. Transp Sci 40:342–350 Gendreau M, Iori M, Laporte G, Martello S (2008) A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51(1):4–18 Hansen P, Mladenovi´c N (2001) Variable neighbourhood search: principles and applications. Eur J Oper Res 130:449–467. Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220:671–680 Iori M, Salazar-González J, Vigo D (2007) An exact approach for the vehicle routing problem with twodimensional loading constraints. Transp Sci 41(2):253–264 Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic, Norwell, pp 321–353. Chap 11 Mladenovi´c N (1995) A variable neighbourhood algorithm, a new metaheuristic for combinatorial optimization. Abstracts of papers presented at optimization days 112, Montréal Mladenovi´c N, Hansen P (1997) Variable neighbourhood search. Comput Oper Res 24:1097–1100 Petersen HL, Madsen OBG (2009) The double travelling salesman problem with multiple stacks—formulation and heuristic solution approaches. Eur J Oper Res (in press)Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget J-F (eds) Principle and practice of constraint programming—CP9 8. Springer,Berlin | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 72ddce0d-fbc4-4233-800c-cbd2cc36a012 | |
| relation.isAuthorOfPublication | 6f9ad449-8cec-4e55-aca2-7dedcde6b101 | |
| relation.isAuthorOfPublication | 9a8e32e5-51d7-41cd-9e5f-781d838bce09 | |
| relation.isAuthorOfPublication.latestForDiscovery | 72ddce0d-fbc4-4233-800c-cbd2cc36a012 |
Download
Original bundle
1 - 1 of 1