Vehicle routing problem with partly simultane-ous pickup and delivery for the cluster of small and medium enterprises

Pengfei HE; Jing LI

doi:10.5604/01.3001.0012.0940

Authors

Pengfei HE Nanjing Agricultural University, Faculty of Engineering, Nanjing, China Author
Jing LI Nanjing Agricultural University, Faculty of Engineering, Nanjing, China Author

DOI:

https://doi.org/10.5604/01.3001.0012.0940

Keywords:

pickup, delivery, small and medium enterprises, transportation service

Abstract

The transportation service for the cluster of small and medium enterprises (SMEs) is different with traditional vehicle routing problems. In the cluster of SMEs, parts of enterprises are pickup and delivery spots simultaneously, but some enterprises are partly pickup and delivery simultaneously. It is necessary to optimize this transportation service with an effective mathematics and algorithm to reduce transportation costs for manufacturers. However, traditional mathematics models and algorithms are not suitable to solve the vehicle routing problem partly simultaneous pickup and delivery (VRPPSD) because these items mainly focus on the vehicle routing problem with pickup and delivery simultaneously. In this paper, a mathematics operational model is proposed to analyze the transportation service of the cluster companies and to describe transportation processes. A hybrid algorithm which is composed by tabu search, genetic algorithm and local search is used to optimize the operational model. The crossover and mutation contained by genetic algorithm are used to generate neighborhood solutions for tabu search, and the local search is used to improve optimizing solutions. The data of a cluster of SMEs, investigating from Changzhou city, China, are employed to show the validity of our mathematical model and algorithm. The results indicate that our model and hybrid algorithm is effective to solve VRPPSD. In this paper, the satisfied solutions of VRPPSD are found by hybrid algorithm. At the same time, the results also show that carriers with optimal routs can service customers with more profits (increasing 5.6%). The potential saving of transport cost will increase profits of carriers in SMEs. Sensitivity analyses about adjusting service time and rate of new orders are lunched to analyze how these two factors influence the profits of the VRPPSPD in a dynamic case. A bottleneck that influences the profits is found, and there has a shorter service time which could increase gross profits, but not significantly.

References

AVCI, M. AND TOPALOGLU, S., 2016. A hybrid metaheuristic algorithm for heterogene-ous vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 53, pp. 160-171.

AVCI, M. AND TOPALOGLU, S., 2015. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Indus-trial Engineering, 83, pp. 15-29.

BRÄYSY, O., AND GENDREAU, M., 2005. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science, 39(1), pp.104-118.

BOONKLEAW, A., SUTHIKARNNAR-UNAI, N. and Srinon, R., 2010. Strategic planning for newspaper delivery problem using vehicle routing algorithm with time window (VRPTW). Engineering Letters, 18(2).

CATTARUZZA, D., ABSI, N., FEILLET, D. AND VIDAL, T. 2014. A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Re-search, 236(3), 833-848.

CORDEAU, J. F., AND MAISCHBERGER, M., 2012 A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39(9), pp. 2033-2050.

GHILAS, V., DEMIR, E. AND VAN WOENSEL, T., 2016. An adaptive large neighbor-hood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines. Computers & Operations Research, 72, pp. 12-30.

GLOVER, F., 1986. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13, pp. 533-549.

IZDEBSKI, M., 2014. The use of heuristic algorithms to optimize the transport issues on the example of municipal services companies. Archives of Transport, 29(1), pp. 27-36

IZDEBSKI, M., JACYNA-GOŁDA, I., MARKOWSKA, K., MURAWSKI, J., 2017. Heuristic algorithms applied to the problems of servicing actors in supply chain. Archive of Transport, 44(4), pp. 25-34.

KALAYCI, C. B. AND KAYA, C., 2016. An ant colony system empowered variable neigh-borhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 66, pp. 163-175.

LI, X. Y., LEUNG, S. C. H. AND TIAN, P., 2012. A multi-start adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. Ex-pert Systems with Applications, 39(1), pp. 365-374.

LI, Y., CHEN, H. X. AND PRINS, C., 2016. Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests. European Journal of Operational Research, 252, pp. 27-38.

LEWCZUK, K. 2015. The concept of genetic programming in organizing internal transport processes. Archives of Transport, 34(2), pp. 61-74.

LIU, R., XIE, X. L., AUGUSTOA, V. AND RODRIGUEZA, C., 2013. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal Operational Research, 230(3), pp. 475-486.

NAGY, G., WASSAN, N. A. AND SALHI, S., 2013. The vehicle routing problem with restricted mixing of deliveries and pickups. Journal of Scheduling, 16(2), pp. 199-213.

SUBRAMANIAN, A., UCHOA, E., PESSOA, A. A. AND OCHI, L. S., 2011. Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39(5), pp. 338-341.

SZCZEPAŃSKI, E., JACYNA-GOŁDA, I. AND MURAWSKI, J., 2014. Genetic algorithms based approach for transhipment hub location in urban areas. Archives of Transport, 31(3), pp. 73-82.

VEENSTRA, M., CHERKESLY, M., DE-SAULNIERS, G. AND LAPORTE, G., 2017. The pickup and delivery problem with time windows and handling operations. Computer & Operations Research, 77, pp. 127-140.

WASSAN, N. A., NAGY, G. AND AHMADI, S., 2008. A heuristic method for the vehicle routing problem with mixed deliveries and pickups. Journal of Scheduling, 11(2), pp. 149-161.

YANG, J., JAILLET, P. AND MAHMAS-SANI, H., 2004. Real-Time Multivehicle Truckload Pickup and Delivery Problems. Transportation Science, 38(2), pp. 135-148.

YU, V. F. AND LIN, S. Y., 2016. Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. International Journal of Production Research, 54(2), pp. 526-549.

ZHANG, T., CHAOVALITWONGSE, W. A. AND ZHANG, Y. J., 2014. Integrated Ant Colony and Tabu Search approach for time de-pendent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 28, pp. 288-309.