https://hal-utt.archives-ouvertes.fr/hal-02521826Chu, FengFengChuLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueLabadie, NacimaNacimaLabadieLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiquePrins, ChristianChristianPrinsLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueThe Periodic Capacitated Arc Routing Problem linear programming model, metaheuristic and lower boundsHAL CCSD2004PCARPlinear programminglower boundtransformed graphscatter search[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]Gavrysiak, Daniel2020-03-27 16:12:422022-06-26 01:39:302020-03-27 16:12:42enJournal articles10.1007/s11518-006-0174-y1The 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.