The modified efficient insertion heuristic that allows multiple trips per vehicle (MEIH-MT) and one that allows a single trip per vehicle with a postprocessing greedy heuristic (MEIH-ST-GH) to construct a multitrip solution are proposed to solve the multitrip vehicle routing problem with time windows and shift time limits. The modifications to the original heuristic enforce the bounds of the forward shift of the earliest departure time of the vehicle and the backward shift of the latest completion time of the vehicle due to an insertion to guarantee a consistent and feasible solution. The overall complexities of both heuristics are the same as those of the original heuristic, O(n3). MEIH-MT and MEIH-ST-GH are performed on 280 instances based on Solomon's test problems. There is no clear winner on the basis of the number of vehicles and total travel time, whereas MEIH-MT is worse than MEIH-ST-GH on computer processing time in all instances. For cluster instances, MEIH-MT should be preferred because it is on average better than MEIH-ST-GH by two criteria: 1.91% on number of vehicles and 0.77% on total travel time. For random-cluster instances, MEIH-MT should be preferred because it is better than MEIH-ST-GH by two criteria: 9.02% on number of vehicles and 5.56% on total travel time. For random instances, MEIH-ST-GH should be preferred because MEIH-MT is outperformed by MEIH-ST-GH by two criteria: 70.92% on processing time and 12.41% on number of vehicles. Thus, MEIH-MT should be preferred over MEIH-ST-GH for the problem instances with clustered customer locations, and MEIH-ST-GH should be preferred for the problem instances with random customer locations.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Efficient Insertion Heuristics for Multitrip Vehicle Routing Problem with Time Windows and Shift Time Limits


    Weitere Titelangaben:

    Transportation Research Record


    Beteiligte:


    Erscheinungsdatum :

    2015-01-01




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Reducing Carbon Emissions with Multitrip Vehicle Mode

    Yu, Yang / Tang, Jiafu / Zhang, Yu et al. | Transportation Research Record | 2014



    Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems

    Campbell, A. M. / Savelsbergh, M. | British Library Online Contents | 2004


    Agents Toward Vehicle Routing Problem With Time Windows

    Kalina, Petr / Vokřínek, Jiří / Mařík, Vladimír | Taylor & Francis Verlag | 2015