A Hybrid Genetic-Simulated Annealing-Auction Algorithm for a Fully Fuzzy Multi-Period Multi-Depot Vehicle Routing Problem

Document Type : Research Paper

Authors

Birjand University of Technology, Birjand, Iran

Abstract

In this paper, an integer linear programming formulation is developed for a novel fuzzy multi-period multi-depot vehicle routing problem. The novelty belongs to both the model and the solution methodology. In the proposed model, vehicles are not forced to return to their starting depots. The fuzzy problem is transformed into a mixed-integer programming problem by applying credibility measure whose optimal solution is an (α,β)-credibility optimal solution to the fuzzy problem. To solve the problem, a hybrid genetic-simulated annealing-auction algorithm (HGSA), empowered by a modern simulated annealing cooling schedule function, is developed. Finally, the efficiency of the algorithm is illustrated by employing a variety of test problems and benchmark examples. The obtained results showed that the algorithm provides satisfactory results in terms of different performance criteria.

Keywords

References

Alonso F., Alvarez M.J. and Beasley J.E. (2008). A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society, Vol. 59, pp.963-976.

Angelelli E. and Speranza M.G. (2002). The periodic vehicle routing problem with intermediate facilities. European journal of Operational research, Vol. 137, pp. 233-247.

Beltrami E.J. and Bodin L.D. (1974). Networks and vehicle routing for municipal waste collection. Networks, Vol.4, pp.65-94.

Blakeley F., Argüello B., Cao B., Hall W. and Knolmajer J. (2003). Optimizing periodic maintenance operations for Schindler Elevator Corporation Interfaces. Interfaces, Vol. 33, pp. 67-79.

Brunelli M. and Mezei J. (2013). How different are ranking methods for fuzzy numbers? A numerical study. International Journal of Approximate Reasoning, Vol. 54, pp. 627-639.
Claassen G., Hendriks T.H. (2007). An application of special ordered sets to a periodic milk collection problem. European Journal of Operational Research, Vol. 180, pp. 754-769.
Crevier B., Cordeau J.-F. and Laporte G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, Vol. 176, pp.756-773.
Das S.K., Roy S.K. and Weber G.W. (2020). Application of type-2 fuzzy logic to a multi-objective green solid transportation-location problem with dwell time under carbon tax, cap and offset policy: Fuzzy vs. Non-fuzzy techniques. IEEE Transactions on Fuzzy Systems, 10.1109/TFUZZ.2020.3011745.
Das S.K., Roy S.K. and Weber G.W. (2020). Heuristic approaches for solid transportation-p-facility location problem. Central European Journal of Operations Research, Vol. 28, pp. 939-961.
Dondo R.G. and Cerdá J. (2009). A hybrid local improvement algorithm for large-scale multi-depot vehicle routing problems with time windows. Computers & Chemical Engineering, Vol. 33, pp.513-530.
Drummond L.M., Ochi L.S. and Vianna D.S. (2001). An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Generation Computer Systems, Vol. 17, pp. 379-386.
Eydi A. and Abdorahimi H. (2012). Model and Solution Approach for Multi-Period and Multi-Depot Vehicle Routing Problem with Flexibility in Specifying the Last Depot of Each Route. International Journal of Industrial Engineering, Vol. 23, pp.333-349.
Freling R., Wagelmans A.P. and Paixão J.M.P. (2001). Models and algorithms for single-depot vehicle scheduling, Transportation Science, Vol. 35, pp. 165-180.
Geman S. and Geman D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, Vol. 6, pp.721-741.
Ghatee M. and Niksirat M. (2013). A Hopfield neural network applied to the fuzzy maximum cut problem under credibility measure. Information Sciences, Vol. 229, 77-93.
Giosa I., Tansini I. and Viera, I. (2002). New assignment algorithms for the multi-depot vehicle routing problem. Journal of the Operational Research Society, Vol. 53, pp. 977-984.
Hasan M.R. and Mashud A.H.M. (2019). An Economic Order Quantity model for decaying products with the frequency of advertisement, selling price and continuous time-dependent demand under partially backlogged shortage. International Journal of Supply and Operations Management (IJSOM), Vol. 6, pp. 296-314.
Hemmelmayr V.C., Doerner K.F., Hartl R.F. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, Vol. 195, 791-802.
Ho W., Ho G.T., Ji P. and Lau H.C. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, Vol. 21, pp. 548-557.
Jalali S. and Boyce J.F. (1995). Determination of optimal general edge detectors by global minimization of a cost function. Image and Vision Computing, Vol. 13, pp. 683-693.
Kang K.H., Lee Y.H. and Lee B.K. (2005). An exact algorithm for multi depot and multi period vehicle scheduling problem. International Conference on Computational Science and Its Applications, Vol. 4, pp. 350-359.
Ke L. and Feng Z. (2013). A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, Vol. 40, pp.633-638.
Kek A.G., Cheu R.L. and Meng Q. (2008). Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Mathematical and Computer Modelling, Vol. 47, pp. 140-152.
Lin J.-S., Liu M. and Huang N.-F. (2000). The shortest path computation in MOSPF protocol using an annealed Hopfield neural network with a new cooling schedule. Information Sciences, Vol. 129, pp.17-30.
Maity G., Mardanya D., Roy S.K. and Weber G.W. (2019). A new approach for solving dual-hesitant fuzzy transportation problem with restrictions. Sādhanā, Vol. 44, pp. 1-11.
Majumder S., Kundu P., Kar S. and Pal T. (2019). Uncertain multi-objective multi-item fixed charge solid transportation problem with budget constraint. Soft Computing, Vol. 23, pp. 3279-3301.
Mashud A.H.M., Hasan M.R., Wee H.M. and Daryanto Y. (2019). Non-instantaneous deteriorating inventory model under the joined effect of trade-credit, preservation technology and advertisement policy. Kybernetes, Vol. 49 (6), pp. 1645-1674.
Mashud A.H.M., Uddin M.S. and Sana S.S. (2019). A Two-Level Trade-Credit Approach to an Integrated Price-Sensitive Inventory Model with Shortages. International Journal of Applied and Computational Mathematics, Vol. 5(4), pp. 1-28.
Midya S., Roy S.K. and Vincent F.Y. (2020). Intuitionistic fuzzy multi-stage multi-objective fixed-charge solid transportation problem in a green supply chain. International Journal of Machine Learning and Cybernetics, Vol. 49, pp. 1-19.
Mohamadi A., Yaghoubi S. and Derikvand H. (2015). A credibility-based chance-constrained transfer point location model for the relief logistics design (Case Study: earthquake disaster on region 1 of Tehran city). International Journal of Supply and Operations Management, 1(4), 466-488.
Nagy G. and Salhi S.D. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research, Vol. 162, pp. 126-141.
Ngueveu S.U., Prins C. and Calvo R.W. (2010). An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research, Vol. 37, pp.1877-1885.
Niksirat M., Hashemi S.M. and Ghatee M. (2016). Branch-and-price algorithm for fuzzy integer programming problems with block angular structure. Fuzzy Sets and Systems, Vol. 296, pp.70-96.
Niksirat M. (2016). Multi-depot vehicle scheduling under fuzzy conditions, Amirkabir Univercity of Thecnology.
Rabbani M., Mokhtarzadeh M. and Farrokhi-Asl, H. (2018). A new mathematical model for designing a municipal solid waste system considering environmentally issues. International Journal of Supply and Operations Management, Vol. 5, pp . 234-255.
Ribeiro G.M. and Laporte G. (2012). An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, Vol.39, pp.728-735.
Roy S.K. and Midya S. (2019). Multi-objective fixed-charge solid transportation problem with product blending under intuitionistic fuzzy environment. Applied Intelligence, 49, 3524-3538.
Saffarian M., Barzinpour F. and Eghbali M.A. (2015). A robust programming approach to bi-objective optimization model in the disaster relief logistics response phase. International Journal of Supply and Operations Management, Vol. 2, pp. 595-616.
Saffarian M., Barzinpour F. and Kazemi S.M. (2017). A Multi-period Multi-objective Location-routing Model for Relief Chain Management under Uncertainty. International Journal of Supply and Operations Management, Vol. 4(4), pp. 298-317.
Sumichras R.T. and Markham I.S. (1995). A heuristic and lower bound for a multi-depot routing problem. Computers & Operations Research, Vol. 22, pp. 1047-1056.
Thangiah S.R. and Salhi S. (2001). Genetic clustering: an adaptive heuristic for the multidepot vehicle routing problem. Applied Artificial Intelligence, Vol. 15, pp. 361-383.
Thomas A.S. and Kopczak L.R. (2005). From logistics to supply chain management: the path forward in the humanitarian sector Fritz Institute. Vol. 15, pp. 1-15.
Van Wassenhove L.N. (2006). Humanitarian aid logistics: supply chain management in high gear. Journal of the Operational Research Society, Vol. 57, pp. 475-489.
Van Wassenhove L.N. and Pedraza Martinez A.J. (2012). Using OR to adapt supply chain management best practices to humanitarian logistics. International Transactions in Operational Research, Vol. 19, pp. 307-322.
Wu T.-H., Low C. and Bai J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, Vol. 29, pp.1393-1415.
International Journal of Supply and Operations Management
Volume 8, Issue 2
May 2021
Pages 96-113

Files

Share

How to cite

Statistics