|
|||||
|
|
| THE PERIODIC CAPACITATED ARC ROUTING PROBLEM LINEAR PROGRAMMING MODEL, METAHEURISTIC AND LOWER BOUNDS | |
| 引用本文： | Nacima LABADI,Christian PRINS. THE PERIODIC CAPACITATED ARC ROUTING PROBLEM LINEAR PROGRAMMING MODEL, METAHEURISTIC AND LOWER BOUNDS[J]. 系统科学与系统工程学报(英文版), 2004, 13(4): 423-435. DOI: 10.1007/s11518-006-0174-y |
| 作者姓名： | Nacima LABADI Christian PRINS |
| 作者单位： | FRE CNRS 2732 ISTIT-OSI University of Technology of Troyes 12 rue Marie Curie，BP2060，10010 Troyes，France，FRE CNRS 2732 ISTIT-OSI University of Technology of Troyes 12 rue Marie Curie，BP2060，10010 Troyes，France |
| 摘 要： | 1. Introduction The Capacitated Arc Routing Problem(CARP) is defined on an undirected network inwhich a fleet of identical vehicles with limitedcapacity is based at a depot node. Each edge hasa non-negative traversal cost and can betraversed any number… |
| 关 键 词： | PCARP 路线选择问题 线性规划 下界 变换图 分散搜寻 |
The Periodic Capacitated Arc Routing Problem linear programming model,metaheuristic and lower bounds |
|
| Feng Chu,Nacima Labadi,Christian Prins. The Periodic Capacitated Arc Routing Problem linear programming model,metaheuristic and lower bounds[J]. Journal of Systems Science and Systems Engineering, 2004, 13(4): 423-435. DOI: 10.1007/s11518-006-0174-y | |
| Authors: | Feng Chu Nacima Labadi Christian Prins |
| Affiliation: | FRE CNRS 2732 ISTIT-OSI University of Technology of Troyes 12 rue Marie Curie, BP2060, 10010 Troyes, France |
| Abstract: | The Periodic Capacitated Arc Routing Problem (PCARP) generalizes the well known NP-hard Capacitated Arc Routing Problem (CARP) by extending the single period to multi-period horizon. The Capacitated Arc Routing Problem (CARP) is defined on an undirected network in which a fleet of identical vehicles is based at a depot node. A subset of edges, called tasks, must be serviced by a vehicle. The CARP consists of determining a set of feasible vehicle trips that minimizes the total cost of traversed edges. The PCARP involves the assignment of tasks to periods and the determination of vehicles trips in each period, to minimize the total cost on the whole horizon. This new problem arises in various real life applications such as waste collection, mail delivery, etc. In this paper, a new linear programming model and preliminary lower bounds based on graph transformation are proposed. A meta-heuristic approach - Scatter Search (SS) is developed for the PCARP and evaluated on a large variety of instances. |
| Keywords: | PCARP linear programming lower bound transformed graph scatter search |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ | |