Column generation based heuristics for a generalized location routing problem with profits arising in space exploration

Jaemyung Ahn, Olivier de Weck, Yue Geng and Diego Klabjan

European Journal of Operational Research, 2012, vol. 223, issue 1, 47-59

Abstract: The generalized location routing problem with profits is a new routing problem class that combines the vehicle routing problem with profits, depot or base selection, and the notion of strategies and route tactics to be employed at selected bases. The problem simultaneously determines base locations, strategies to use at the bases, sites to visit, and routes to carry out the visits, to maximize the sum of profits that can be obtained by visiting sites, under resource consumption constraints. The problem arises in exploration of planetary bodies where strategies correspond to different technologies. A description of the generalized location routing problem with profits and its mathematical formulation as an integer program are provided. Two solution methodologies to solve the problem – branch-and-price and a three-phase heuristic method combined with a generalized randomized adaptive search procedure – are proposed. Numerical experiments for the two solution methodologies are carried out. Their performance in terms of computation time and optimality gap are analyzed and compared to establish the problem characteristics, indicating which method is more advantageous.

Keywords: Heuristics; Branch and bound; Routing; Location; Transportation; Logistics (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712004730
Full text for ScienceDirect subscribers only

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:eee:ejores:v:223:y:2012:i:1:p:47-59

DOI: 10.1016/j.ejor.2012.06.018

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().