Abstract The time-dependent pollution routing problem (TDPRP) extends the pollution routing problem (PRP) cause it captures traffic congestion at peak periods in urban transportation. It concerns planning a fleet of homogeneous vehicles to serve all customers, jointly deciding their speed on every arc and the departure time from each node such that the total cost of routes reaches a minimum. To our knowledge, all solution methods for the TDPRP are founded on (meta-)heuristics. In this study, we propose an exact branch-and-price-and-cut (BPC) algorithm for the TDPRP. The master problem is a route selection problem formulated as a set-partitioning model, and the pricing problem is a time-dependent elementary shortest path problem with resource constraints (TDESPPRC), in which the speed and start time at each customer need to be decided. We devise a tailored label-setting algorithm to handle the pricing problem, and the master problem is solved by column generation. Then, two valid inequalities are employed to tighten the lower bound, and several accelerating techniques are used to speed up the label-setting algorithm. Meanwhile, we present an analytical characterization applied to different scenarios. Finally, extensive computational experiments show our algorithm outperform a commercial MIP solver, and the optimal solutions are found for more benchmark instances using less time.

    Highlights This paper presents an exact solution based on a BPC algorithm for the TDPRP. The corresponding pricing problem is a TDESPPRC, which is tailored to solve by a label-setting algorithm. This paper introduces an easy-to-check dominance rule by exploiting the structure of the departure time and the total cost function. The extensive computational experiments show the effectiveness and efficiency of our algorithm. Our new dominance idea could be used to effectively solve the pricing problems of other VRP variants, where the dominance test needs to compare functions, for example, the PRP, the VRPSTW and the TDVRP.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A branch-and-price-and-cut algorithm for time-dependent pollution routing problem


    Beteiligte:
    Gao, Wenqi (Autor:in) / Luo, Zhixing (Autor:in) / Shen, Houcai (Autor:in)


    Erscheinungsdatum :

    2023-09-08




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows

    Dabia, S. / Ropke, S. / van Woensel, T. et al. | British Library Online Contents | 2013



    Branch-and-price algorithm for the location-routing problem with time windows

    Ponboon, Sattrawut / Qureshi, Ali Gul / Taniguchi, Eiichi | Elsevier | 2015


    The time-dependent pollution-routing problem

    Franceschetti, Anna | Online Contents | 2013