Integer Programming Based Approaches for Multi-Trip Location Routing

Rita Macedo (), Bruna Ramos (), Cláudio Alves (), José Valério Carvalho (), Saïd Hanafi () and Nenad Mladenović ()
Additional contact information
Rita Macedo: Université de Valenciennes
Bruna Ramos: Universidade do Minho
Cláudio Alves: Universidade do Minho
José Valério Carvalho: Universidade do Minho
Saïd Hanafi: Université de Valenciennes
Nenad Mladenović: Université de Valenciennes

A chapter in Computational Management Science, 2016, pp 79-90 from Springer

Abstract: Abstract The multi-trip location routing problem consists in selecting the depots to open and the routes that should be performed to serve a set of clients at minimum cost. The multi-trip variant considers the possibility for a vehicle to perform more than a single route during the planning period, and hence it applies typically to cases in which the trips are performed within a small geographic area and involves for example the transportation of perishable goods. As a consequence, the inherent complexity of the problem increases as it has now to determine which routes should be assigned to the vehicles. In this paper, we explore an improved network flow formulation for this problem, and we compare it with another compact formulation proposed in the literature. We describe also an iterative rounding heuristic that relies on this model. We show through computational experiments on benchmark instances that the model provides good lower bounds, and that it can be used both by commercial solvers and heuristics to derive good quality solutions for the problem.

Keywords: Column Generation; Planning Period; Valid Inequality; Linear Relaxation; Benchmark Instance (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnechp:978-3-319-20430-7_11

Ordering information: This item can be ordered from
http://www.springer.com/9783319204307

DOI: 10.1007/978-3-319-20430-7_11

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().