Projection results for vehicle routing

• 成果类型: Article; Proceedings Paper
• 署名作者: Letchford, AN; Salazar-González, JJ
• 署名单位: Lancaster University; Universidad de la Laguna
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0652-x
• 发表日期: 2006
• 页码: 251-274
• 关键词: traveling salesman problem; time windows; flow formulation; branch; algorithm

摘要

A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and Graves yields, by projection, certain `multistar' inequalities in the two-index space. We give a survey of formulations for the capacitated VRP, and then present various results of a similar flavour to those of Gouveia. In particular, we show that: - the three-index formulation, augmented by certain families of valid inequalities, gives the same lower bound as the two-index formulation, augmented by certain simpler families of valid inequalities, - the two-commodity flow formulation of Baldacci et al. gives the same lower bound and the same multistar inequalities as the one-commodity Gavish and Graves formulation, - a certain non-standard multi-commodity flow formulation, with one commodity per customer, implies by projection certain `hypotour-like' inequalities in the two-index space, - the set partitioning formulation implies by projection both multistar and hypotour-like inequalities in the two-index space. We also briefly look at some other variants of the VRP, such as the VRP with time windows, and derive multistar-like inequalities for them. We also present polynomial-time separation algorithms for some of the new inequalities.