The vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehiclesof limited capacity and the customers can be visited in any order. We study how the branch-and-price technique can be applied to the solution of this problem and in particular we compare two different ways of solving the pricing subproblem: exact dynamic programming and state space relaxation. By applying a bidirectional search we experimentally prove its effectiveness in solving the subproblem. We also devise suitable branching strategies for both the exact and the relaxed approach and we report on an extensive set of computational experiments on benchmark instances with both simple and composite demands.

A Branch and Price Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery / Dell'Amico, Mauro; G., Righini; M., Salani. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 40:2(2006), pp. 235-247. [10.1287/trsc.1050.0118]

A Branch and Price Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery

DELL'AMICO, Mauro;
2006

Abstract

The vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehiclesof limited capacity and the customers can be visited in any order. We study how the branch-and-price technique can be applied to the solution of this problem and in particular we compare two different ways of solving the pricing subproblem: exact dynamic programming and state space relaxation. By applying a bidirectional search we experimentally prove its effectiveness in solving the subproblem. We also devise suitable branching strategies for both the exact and the relaxed approach and we report on an extensive set of computational experiments on benchmark instances with both simple and composite demands.
2006
40
2
235
247
A Branch and Price Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery / Dell'Amico, Mauro; G., Righini; M., Salani. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - STAMPA. - 40:2(2006), pp. 235-247. [10.1287/trsc.1050.0118]
Dell'Amico, Mauro; G., Righini; M., Salani
File in questo prodotto:
File Dimensione Formato  
23830217.pdf

Accesso riservato

Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 148.45 kB
Formato Adobe PDF
148.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/451197
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 161
  • ???jsp.display-item.citation.isi??? 133
social impact