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

Jaemyung Ahn, Olivier De Weck, Yue Geng*, Diego Klabjan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)47-59
Number of pages13
JournalEuropean Journal of Operational Research
Volume223
Issue number1
DOIs
StatePublished - Nov 16 2012

Keywords

  • Branch and bound
  • Heuristics
  • Location
  • Logistics
  • Routing
  • Transportation

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Column generation based heuristics for a generalized location routing problem with profits arising in space exploration'. Together they form a unique fingerprint.

Cite this