A multi-stop routing problem

被引：0
作者：
Jose Luis Gonzalez-Velarde
Salvador Garcia-Lumbreras
Alberto Garcia-Diaz
机构：
[1] Tecnológico de Monterrey,
[2] The University of Tennessee,undefined
来源：
Annals of Operations Research | 2008年 / 157卷
关键词：
Routing; Mixed integer programming; Valid inequalities;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included.
引用
收藏
页码：153 / 167
页数：14
相关论文
共 24 条
[1]  
Balas E.(1975)Facets of the knapsack polytope Mathematical Programming 8 146-164
[2]  
Chuah K. H.(2005)Routing for a just-in-time supply pickup and delivery system Transportation Science 39 328-339
[3]  
Yingling J. C.(2002)Heuristic solutions to the problem of routing school buses with multiple objectives Journal of the Operational Research Society 53 427-435
[4]  
Corberán A.(1993)Polyhedral study of the capacitated routing problem Mathematical Programming 60 21-53
[5]  
Fernández E.(1956)The traveling salesman problem Operations Research 4 23-34
[6]  
Laguna M.(2004)Dispatching of an electric monorail system: applying metaheuristics to an online pickup and delivery problem Transportation Science 38 434-446
[7]  
Martí R.(2006)Tabu search for a multi-objective routing problem Journal of the Operational Research Society 57 29-37
[8]  
Cornuejols D.(1976)An optimization approach to routing aircraft Transportation Science 11 170-188
[9]  
Harsche R.(1995)The pick-up and delivery problem Transportation Science 29 18-30
[10]  
Flood M.(1986)Valid inequalities for mixed zero–one programs Discrete Applied Mathematics 14 199-213
123