OPTIMIZING THE PROCESS OF PICK-UP AND DELIVERY WITH TIME WINDOWS USING ANT COLONY AND TABU SEARCH ALGORITHMS
Abstract
The provision of goods shuttle services sometimes faces several constraints, such as the limitation on the number of vehicles, vehicle capacity, and service time, or the vehicle used has single transport access. To avoid losses, a strategy is needed in determining the optimal route and policy for arranging goods in the vehicle especially if there are two types of goods involved. Traveling Salesman Problem and Pick-up and Delivery with Handling Costs and Time Windows (TSPPDHTW) is a model of an optimization problem that aims to minimize the total travel and goods handling costs in the goods pick-up and delivery with the constraints previously mentioned. Solving that model using the exact method requires a very long computation time so it’s not effective to be implemented in real-life. This study aims to develop a (meta)heuristic based on Ant Colony Optimization (ACO) and Tabu Search (TS) to be ACOTS to solve TSPPDHTW with reasonable computation time. The development is carried out by adding functions of clustering, evaluating constraints, cutting tours, arranging of goods, and evaluating moves on the TS, as well as modifying transition rules. The result has a deviation of about 22% and 99.99% less computational time than the exact method.
Downloads
References
I. S. Amalia, T. Bakhtiar, and Jaharuddin, “Minimizing the handling time in VRP with pickup-and-delivery and time windows,” J. Phys. Conf. Ser., vol. 1863, no. 1, 2021, doi: 10.1088/1742-6596/1863/1/012002.
P. Guo, M. Hou, and L. Ye, “MEATSP: A Membrane Evolutionary Algorithm for Solving TSP,” IEEE Access, vol. 8, pp. 199081–199096, 2020, doi: 10.1109/ACCESS.2020.3035058.
K. E. Adetunji, I. W. Hofsajer, A. M. Abu-Mahfouz, and L. Cheng, “A Review of Metaheuristic Techniques for Optimal Integration of Electrical Units in Distribution Networks,” IEEE Access, vol. 9, pp. 5046–5068, 2021, doi: 10.1109/ACCESS.2020.3048438.
J. Kozak, Studies in Computational Intelligence 781: Decision Tree and Ensemble Learning Based on Ant Colony Optimization. 2019. [Online]. Available: http://www.springer.com/series/7092
M. S. Umam, M. Mustafid, and S. Suryono, “A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem,” J. King Saud Univ. - Comput. Inf. Sci., no. xxxx, 2021, doi: 10.1016/j.jksuci.2021.08.025.
J. J. De La Cruz, C. D. Paternina-Arboleda, V. Cantillo, and J. R. Montoya-Torres, “A two-pheromone trail ant colony system - Tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products,” J. Heuristics, vol. 19, no. 2, pp. 233–252, 2013, doi: 10.1007/s10732-011-9184-0.
S. Hanif, “RESEARCH PAPERS TRAVELLING SALESMEN PROBLEM SOLUTION WITH ANT-COLONY,” vol. 14, no. 2, pp. 1–9, 2020.
R. W. Dewantoro, P. Sihombing, and Sutarman, “The Combination of Ant Colony Optimization (ACO) and Tabu Search (TS) Algorithm to Solve the Traveling Salesman Problem (TSP),” 2019 3rd Int. Conf. Electr. Telecommun. Comput. Eng. ELTICOM 2019 - Proc., pp. 160–164, 2019, doi: 10.1109/ELTICOM47379.2019.8943832.
M. Diallo, A. Quintero, and S. Pierre, “An Efficient Approach Based on Ant Colony Optimization and Tabu Search for a Resource Embedding across Multiple Cloud Providers,” IEEE Trans. Cloud Comput., vol. 9, no. 3, pp. 896–909, 2021, doi: 10.1109/TCC.2019.2904227.
Q. Li, W. Tu, and L. Zhuo, “Reliable rescue routing optimization for urban emergency logistics under travel time uncertainty,” ISPRS Int. J. Geo-Information, vol. 7, no. 2, 2018, doi: 10.3390/ijgi7020077.
A. Lipowski and D. Lipowska, “Roulette-wheel selection via stochastic acceptance,” Phys. A Stat. Mech. its Appl., vol. 391, no. 6, pp. 2193–2196, 2012, doi: 10.1016/j.physa.2011.12.004.
Z. Zhang, Z. Xu, S. Luan, X. Li, and Y. Sun, “Opposition-based ant colony optimization algorithm for the traveling salesman problem,” Mathematics, vol. 8, no. 10, pp. 1–16, 2020, doi: 10.3390/MATH8101650.
W. Deng, J. Xu, Y. Song, and H. Zhao, “An effective improved co-evolution ant colony optimisation algorithm with multi-strategies and its application,” Int. J. Bio-Inspired Comput., vol. 16, no. 3, pp. 158–170, 2020, doi: 10.1504/IJBIC.2020.111267.
C. K. Teoh, A. Wibowo, and M. S. Ngadiman, “Review of state of the art for metaheuristic techniques in Academic Scheduling Problems,” Artif. Intell. Rev., vol. 44, no. 1, pp. 1–21, 2015, doi: 10.1007/s10462-013-9399-6.
S. A. Fahmy, B. A. Alahlani, and T. F. Abdelmazuid, “A tabu search approach for designing shopping centers,” 2017 9th IEEE-GCC Conf. Exhib. GCCCE 2017, 2018, doi: 10.1109/IEEEGCC.2017.8447954.
L. Pan, X. Liu, Y. Xia, and L. N. Xing, “Tabu Search Algorithm for the Bike Sharing Rebalancing Problem,” IEEE Access, vol. 8, pp. 144543–144556, 2020, doi: 10.1109/ACCESS.2020.3011844.
S. Basu, “Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey,” Am. J. Oper. Res., vol. 02, no. 02, pp. 163–173, 2012, doi: 10.4236/ajor.2012.22019.
M. Gmira, M. Gendreau, A. Lodi, and J. Y. Potvin, “Tabu search for the time-dependent vehicle routing problem with time windows on a road network,” Eur. J. Oper. Res., vol. 288, no. 1, pp. 129–140, 2021, doi: 10.1016/j.ejor.2020.05.041.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
