SOLUTION APPROACHES FOR MIXED PALLET COLLECTION PROBLEM: A CASE STUDY IN A LOGISTIC COMPANY

Year 2019, Volume: 37 Issue: 3, 827 - 840, 01.09.2020

Saadettin Erhan Kesen Muzaffer Alım

Abstract

In this paper, we study a mixed pallet collection problem in a warehouse of the company operating in fast moving consumer goods industry and present a mixed integer programming formulation with the objective function of total travelling distance minimization. The problem studied is shown to be equivalent to the well-known vehicle routing problem. Since the problem belongs to the class of NP-hard problems, introduced mathematical formulation cannot provide optimal solution in an acceptable amount of time. We, therefore, develop an algorithm based on Simulated Annealing (SA) meta-heuristic approach to find near-optimal solution in a quite shorter computational time. Routes are constructed using Clarke&Wright saving algorithm and then these routes are perturbed whereby three neighborhood operators, namely swap, insert, swap-range are utilized to further improve the quality of the solution. Experimental results based on a real case instance demonstrates that SA algorithm is capable of providing solution more quickly than that of CPLEX solver but the quality of the solution found by SA is 7% worse than that of CPLEX.

Keywords

Vehicle routing problem, Clarke and Wright saving algorithm, simulated annealing

References

• [1] Şahin Y., Eroğlu A., Kapasite Kısıtlı Araç Rotalama Problemi İçin Meta Sezgisel Yöntemler Bilimsel Yazın Taraması, Süleyman Demirel Üniversitesi İktisadi ve İdari bilimler Fakültesi Dergisi, 19(4), 337-355, 2014.
• [2] Dantzig G., Ramser J., The Truck Dispatching Problem, Management Science, 6(1), 80-91, 1959.
• [3] Clarke G., Wright J.W., Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568-581, 1964.
• [4] Golden B.L., Magnanti T.L., Nguyen H.Q., Implementing vehicle routing algorithms, Networks, 7(2), 113–148, 1972.
• [5] Solomon M., Vehicle routing and scheduling with time window constraints: Models and algorithms, Techinical Report, Northeastern University College of Business Admin, 1983.
• [6] Min H., The multiple vehicle routing problem with simultaneous delivery and pickup points, Transportation Research, 23(5), 377–386, 1989.
• [7] Dethloff J., Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23(1), 2001, 79–96, 2001.
• [8] Bayrak A., Özyörük B.,, Bölünmüş talepli eş zamanlı topla dağıt araç rotalama problemi için karşılaştırmalı matematiksel modeller, Journal of the Faculty of Engineering and Architecture of Gazi University, 32(2), 469-479, 2017.
• [9] Belbağ, S., Yeşil kapasite kısıtlı araç rotalama problemi:Bir literatür taraması, Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi,19(1), 345-366, 2017.
• [10] Cook T. M., Russell R. A., A simulation and statistical analysis of stochastic vehicle routing with timing constraints, Decision Sciences, 9(4), 673–687, 1978.
• [11] Powell W. B., A stochastic model of the dynamic vehicle allocation problem, Transportation Science, 120(2), 117–129, 1986.
• [12] Brandao J., Mercer A., A Tabu search algorithm for the multi-trip vehicle routing and scheduling problem, European Journal of Operational Research, 100(1), 180–192, 1997.
• [13] Christofides N.,Vehicle scheduling and routing, Presented at the 12th International Symposium on Mathematical Programming, 1985.
• [14] Laporte G., Nobert Y., Exact Algorithms for the Vehicle Routing Problem, North-Holland Mathematics Studies, 132, 147-184, 1987.
• [15] Laporte G.,The Vehicle Routing Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59(3), 345-358, 1992.
• [16] Foster B.A., Ryan D.M., “An integer programming approach to the vehicle scheduling problem”, Operational Research Quarterly, 27(2), 367-384, 1976.
• [17] Gillet B.E., Miller L.R., “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, 22(2), 340-349, 1974.
• [18] Christofides N., Mingozzi A., Toth P., The Vehicle Routing Problem In Combinatorial Optimization, Wiley Chichester, 1979.
• [19] Renaud J., Boctor F.F., Laporte G., An Improved Petal Heuristic for the Vehicle Routing Problem, Journal of Operational Research Society, 47(2), 329-336 , 1996.
• [20] Laporte, G., Ropke, S., & Vidal, T. Heuristics for the vehicle routing problem. Vehicle Routing: Problems, Methods, and Applications, 18, 87, 2014.
• [21] Hopfield, J.J., Tank, D.W.,Neural Computation of Decisions in Optimization Problems. Biological Cybernetics, 52, 141-152,1985.
• [22] Glover F., McMillan C., The General Employee Scheduling Problem: An Integration of Management Science and Artificial Intelligence, Computers and Operations Research, 13(5), 563-593, 1986.
• [23] Kirkpatrick S.Gelatt Jr. C.D., Vecchi M.P., Optimization by simulated annealing, Science, 220(4598), 671–680, 1983.
• [24] Holland J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
• [25] Dorigo M., Maniezzo V., Colorni A., Positive Feedback as a Search Strategy, Technical Report, 91-016, 1991.
• [26] Wang C., Dong M., Zhao F., Sutherland J.W., A Parallel Simulated Annealing Method For The Vehicle Routing Problem With Simultaneous Pickup–Delivery And Time Windows, Computers And Industrial Engineering, 83,111-122, 2015.
• [27] Gendreau M., Guertin F., Potvin J.Y. Seguin R., Neighborhood Search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Transport Research Part C: Emerging Techologies, 14(3), 157-174, 2006.
• [28] Bortfeldt A., A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, Computers & Operations Research, 39(9), 2248-2257, 2012.
• [29] Mester, D., Braysy, O., Active-guided evolution strategies for large-scale capacitated vehicle routing problems, Computers & Operations Research,34 (10), 2964-2975, 2007.
• [30] Aziz E., An Algorithm for the Vehicle Problem, International Journal of Advanced Robotic Systems, 7(2), 125-132, 2010.
• [31] Edison E., Shima T., Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms, Computers & Operations Research, 38(1), 340-356, 2011.
• [32] Günther ,O., Kulak, O., Kalayci ,C. B. ve Polat , O., A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 242, 369-382, 2015.
• [33] Junqueira, L., & Morabito, R. Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier. Computers & Industrial Engineering, 88, 110–130, 2015.
• [34] Pollaris, H., Braekers, K., Caris, A., Janssens, G. K., & Limbourg, S., Vehicle routing problems with loading constraints: state-of-the-art and future directions, OR Spectrum, 37(2), 297–330, 2015.