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

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.

► Introduction, motivation from a real-world application.
► Modeling of a new routing problem, which combines two threads in vehicle routing.
► A heuristic branch-and-price algorithm, relying on tailored branching.
► A novel heuristic combining price-and-branch, GRASP, and integer programming.
► A study of a real-world case encountered in space exploration.