In this paper we introduce the vehicle routing problem with simultaneous pickup and delivery and handling costs (VRPSPD-H). In the VRPSPD-H, a fleet of vehicles operates from a single depot to service all customers, which have both a delivery and a pickup demand such that all delivery items originate from and all pickup items go to the depot. The items on the vehicles are organized as a single linear stack where only the last loaded item is accessible. Handling operations are required if the delivery items are not the last loaded ones. We implement a heuristic handling policy approximating the optimal decisions for the handling sub-problem, and we propose two bounds on the optimal policy, resulting in two new myopic policies. We show that one of the myopic policies outperforms the other one in all configurations, and that it is competitive with the heuristic handling policy if many routes are required. We propose an adaptive large neighborhood search (ALNS) metaheuristic to solve our problem, in which we embed the handling policies. Computational results indicate that our metaheuristic finds optimal solutions on instances of up to 15 customers. We also compare our ALNS metaheuristic against best solutions on benchmark instances of two special cases, the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and the traveling salesman problem with pickups, deliveries and handling costs (TSPPD-H), and on two related problems, the vehicle routing problem with divisible pickup and delivery (VRPDPD) and the vehicle routing problem with mixed pickup and delivery (VRPMPD). We find or improve 39 out of 54 best known solutions (BKS) for the VRPSPD, 36 out of 54 BKS for the VRPDPD, 15 out of 21 BKS for the VRPMPD, and 69 out of 80 BKS for the TSPPD-H. Finally, we introduce and analyze solutions for the variations of the VRPDPD and VRPMPD with handling costs – the VRPDPD-H and the VRPMPD-H, respectively.


    Access

    Download


    Export, share and cite



    Title :

    The vehicle routing problem with simultaneous pickup and delivery and handling costs



    Publication date :

    2020-03-01


    Remarks:

    Hornstra , R P , Silva , A , Roodbergen , K J & Coelho , L C 2020 , ' The vehicle routing problem with simultaneous pickup and delivery and handling costs ' , Computers & Operations Research , vol. 115 , 104858 . https://doi.org/10.1016/j.cor.2019.104858



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    000



    Developing Genetic Algorithm to Solve Vehicle Routing Problem with Simultaneous Pickup and Delivery

    Amir Masoud Rahimi / Vahid Rajabi / Ehsan Ramezani Khansari | BASE | 2020

    Free access

    A Modified Meta-Heuristic Approach for Vehicle Routing Problem with Simultaneous Pickup and Delivery

    Faiz, Alfian / Subiyanto, Subiyanto / Arief, Ulfah Mediaty | BASE | 2018

    Free access

    An Electric Vehicle Routing Problem with Pickup and Delivery

    Yang, Qian-qian / Hu, Da-wei / Chu, Hong-fan et al. | ASCE | 2018


    Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands

    Nadizadeh, Ali / Kafash, Behzad | Taylor & Francis Verlag | 2019