The Capacitated Arc Routing Problem (CARP) involves the routing of vehicles to service a set of arcs in a network. This NP-hard problem is extended to a multiperiod horizon, giving a new tactical problem called the Periodic CARP (PCARP). This problem actually occurs in municipal waste collection. Its objective is to assign arcs to periods and to compute the trips in each period, to minimize an overall cost on the horizon. An integer linear program, two insertion heuristics and a two-phase heuristic are developed. These very first algorithms for the PCARP are evaluated on PCARP instances derived from standard CARP benchmarks from literature: the insertion heuristics are very fast but the two-phase method yields better solution costs. The CARP consists of determining a set of feasible vehicle trips that minimizes the total cost of traversed edges. Each trip starts and ends at the depot, each edge is serviced by one single vehicle and the total demand serviced by any trip must not exceed vehicle capacity. The PCARP (Periodic CARP) is a periodic version of the CARP, defined recently by Lacomme et al. (2002) to model important applications like municipal waste collection. The PCARP can be compared to the Periodic Vehicle Routing Problem (PVRP), in which the tasks are located on nodes instead of arcs. Among the three heuristics proposed, the lower bound method LBH clearly outperforms the two insertion methods, but at the expense of an in creased running time. The disappointing results of insertion techniques (compared to similar heuristics for the Travelling Salesman Problem) can be explained by t5he simultaneous insertion of each task into several days. Further research is required on the PCARP, for instance there is clearly a need for a good lower bound to evaluate the quality of heuristic solutions.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Heuristics for the periodic capacitated arc routing problem


    Additional title:

    Heuristik zur Optimierung des Flottenmanagements kommunaler Entsorgungsfahrzeuge


    Contributors:

    Published in:

    Publication date :

    2005


    Size :

    9 Seiten, 2 Tabellen, 13 Quellen




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English




    The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics

    Perboli, G. / Tadei, R. / Vigo, D. | British Library Online Contents | 2011



    Capacitated arc routing problem with extensions

    Qiao, H. / Haghani, A. | British Library Conference Proceedings | 2005


    Capacitated vehicle routing problem model for carriers

    Irma-Delia Rojas-Cuevas / Santiago-Omar Caballero-Morales / Jose-Luis Martinez-Flores et al. | DOAJ | 2018

    Free access

    Capacitated-Vehicle Routing Problem with Backhauls on Trees

    Kumar, Roshan / Unnikrishnan, Avinash / Waller, S. Travis | Transportation Research Record | 2011