DOI : https://doi.org/10.18517/ijaseit.10.4.10234

Vehicle Routing Problem with Simultaneous Pickup and Delivery

San Nah Sze (1), Siaw Ying Doreen Sek (2), Jeeu Fong Sze (3), Wai Shiang Cheah (4), Kang Leng Chiew (5)
(1) Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak, Kota Samarahan, 94300, Sarawak, Malaysia
(2) Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak, Kota Samarahan, 94300, Sarawak, Malaysia
(3) Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak, Kota Samarahan, 94300, Sarawak, Malaysia
(4) Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak, Kota Samarahan, 94300, Sarawak, Malaysia
(5) Faculty of Computer Science and Information Technology, Universiti Malaysia Sarawak, Kota Samarahan, 94300, Sarawak, Malaysia
Fulltext View | Download
How to cite (IJASEIT) :
[1]
S. N. Sze, S. Y. D. Sek, J. F. Sze, W. S. Cheah, and K. L. Chiew, “Vehicle Routing Problem with Simultaneous Pickup and Delivery”, Int. J. Adv. Sci. Eng. Inf. Technol., vol. 10, no. 4, pp. 1360–1366, Aug. 2020.
Citation Format :
This paper focuses on the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) issue. VRPSPD is one of the extended problems related to the usual Vehicle Routing Problem (VRP). VRPSPD consists of both linehaul customers and backhaul customers with a known demand. In VPRSPD, only a single depot can receive and supply the loads. The vehicles can only visit each customer once and can serve all customers simultaneously by delivering or picking up the loads within a limited capacity. VPRSPD is a NP-hard problem. The huge data size has increased the difficulty for it to be solved by using mathematical programming or combinatorial optimisation. A heuristic approach based on the Variable Neighbourhood Search (VNS) is proposed. Heuristic based solutions offer feasible solutions that are approximately accurate to the exact solution. It is one of the most popular solutions to solve a complex problem. In this research, the algorithm solution consists of two main phases. A simple heuristic is used to generate the initial solution in the first phase. Then, the feasible solution obtained in the first phase will become the initial input for the improvement phase which applied the VNS algorithm. The proposed algorithm is tested using a list of benchmark dataset. The result obtained is compared with the best solution that can be found from the literature research. The comparison result shows that the heuristic algorithm is favourable to be used for this kind of vehicle routing problem.

Anbuudayasankar, S. P., Ganesh, K., & Mohapatra, S. (2016). Models for practical routing problems in logistics. Springer International Pu.

Bianchessi, N., & Righini, G. (2007). Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 34(2), 578-594.

Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.

Chen, P., Golden, B., Wang, X., & Wasil, E. (2017). A novel approach to solve the split delivery vehicle routing problem. International Transactions in Operational Research, 24(1-2), 27-41.

Clarke, G., & Wr23ight, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.

Dong, G., Tang, J., Lai, K. K., & Kong, Y. (2011). An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model. Journal of Intelligent Manufacturing, 22(5), 789-799.

Ehmke, J. F., Campbell, A. M., & Thomas, B. W. (2016). Vehicle routing to minimize time-dependent emissions in urban areas. European Journal of Operational Research, 251(2), 478-494.

Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L. M. (2016). A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, 249(1), 55-66.

Gayialis, S. P., & Tatsiopoulos, I. P. (2004). Design of an IT-driven decision support system for vehicle routing and scheduling. European Journal of Operational Research, 152(2), 382-398.

Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm-harmony search. Simulation, 76(2), 60-68.

Goetschalckx, M., & Jacobs-Blecha, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1), 39-51.

Hansen, P., Mladenović, N., & Pí©rez, J. A. M. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, 175(1), 367-407.

Koí§, í‡, & Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39, 154-164.

Lalla-Ruiz, E., Expósito-Izquierdo, C., Taheripour, S., & VoíŸ, S. (2016). An improved formulation for the multi-depot open vehicle routing problem. OR spectrum, 38(1), 175-187.

Norouzi, N., Sadegh-Amalnick, M., & Tavakkoli-Moghaddam, R. (2017). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11(1), 121-134.

Pinto, T., Alves, C., & de Carvalho, J. V. (2017). Variable neighborhood search algorithms for pickup and delivery problems with loading constraints. Electronic Notes in Discrete Mathematics, 58, 111-118.

Tian, X., Geng, Y., Zhong, S., Wilson, J., Gao, C., Chen, W., & Hao, H. (2018). A bibliometric analysis on trends and characters of carbon emissions from transport sector. Transportation Research Part D: Transport and Environment, 59, 1-10.

Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858.

Wang, J., Zhou, Y., Wang, Y., Zhang, J., Chen, C. P., & Zheng, Z. (2016). Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms. IEEE transactions on cybernetics, 46(3), 582-594.

Wassan, N., Wassan, N., Nagy, G., & Salhi, S. (2017). The multiple trip vehicle routing problem with backhauls: Formulation and a two-level variable neighbourhood search. Computers & Operations Research, 78, 454-467.

Xiao, Y., & Konak, A. (2017). A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem. Journal of Cleaner Production, 167, 1450-1.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).