Compact formulations for multi-depot routing problems: Theoretical and computational comparisons. (December 2020)

• Record Type: Journal Article
• Authors: Bektaş, Tolga; Gouveia, Luís; Santos, Daniel
• Is Part Of: Computers & operations research. Volume 124(2020)
• Publication Date: 2020-12
• Subjects: Vehicle routing -- Multi-depot -- Location-routing -- Integer linear programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105084
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We review and propose new compact formulations for multi-depot routing problems. We study two variants, one with depot selection decisions, and one without. We provide comprehensive theoretical and practical comparisons of the formulations. We offer suggestions on which formulations perform better computationally. Abstract: Multi-depot routing problems mainly arise in distribution logistics where a fleet of vehicles are used to serve clients from a number of (potential) depots. The problem concerns deciding on the routes of each vehicle and the depots from which the vehicles depart, so as to minimize the total cost of travel. This paper reviews a number of existing compact formulations, and proposes new ones, for two types of multi-depot routing problems, one that includes the depot selection decisions, and the other where depots are pre-selected. The formulations are compared theoretically in terms of the strength of their linear programming relaxation, and computationally in terms of the running time needed to solve the instances to optimality.