|
Genetic Algorithm Optimization for Postal Items Pickup and Delivery
|
MohammadReza Joneidi *   , Javad Saberian |
|
|
|
Abstract: (786 Views) |
Introduction: With the growth of urbanization, urban transportation has become one of the most critical challenges of urban management, which is closely related to the economic power of cities and countries. A robust economy requires adequate infrastructure in the freight division, and proper resource planning and management is the key to its success. In this research, the issue of transportation of postal items has been considered. The use of traditional methods prolongs receiving and delivering postal items and thus increases its costs. In this research, this issue has been studied. Using meta-heuristic algorithms (Artificial Intelligence), an attempt has been made to optimize the problem of receiving and delivering postal items.
Materials & Methods: The proposed method of this research is based on the use of a Genetic Algorithm to optimize the order of pickup and delivery of postal items using the travel cost matrix between the points of pickup and delivery. The genetic algorithm has high flexibility following the structure of different problems. In the developed model of this research, the order of picking and delivering shipments in each freight vehicle is in one array and five arrays representing five freight vehicles from five postal centers in one matrix created. The genetic algorithm tries to optimize the final solution by randomly generating these matrices (chromosomes) and measuring the fitness function of each matrix (answer) and using the combination and mutation operators. Finally, the best solution is obtained, which is the best arrangement and planning for the trucks carrying the items, in which the best order of receiving and delivering the postal items is determined.
Results & Discussion: The study area is 10, 11, 12, 14, 15, 16, 17, and 19 regions of Tehran (the capital of Iran), which were selected for implementation. Street network data was entered into the Network Analyst tool in ArcGIS software. Travel cost matrices between pickup and delivery points and consignment centers were extracted from the data of 50 pickup points and 50 delivery points entered into the developed model. After executing the algorithm for 1000 times and generating final output, which is the most optimal arrangement of pickup and delivery points, it was compared with the first random answer made in the model which represents old unplanned method for receiving and delivering the postal items. The total length of final optimal answer is 551689 meters, which is less than 720287 meters (the total length of first random answer). The decrease in the final solution in comparison to the first random solution is 168598 meters, which is equivalent to 24% savings and indicates the efficiency of the developed model.
Conclusion: Using old traditional experimental methods for pick-up and delivery of postal items leads to increase the route of postal vehicles which increase the urban congestion and produces some pollutions. Applying the scientific methods such as used model in this research helps to decrease the aforementioned problems and it is a key to approach the smart cities. We used a genetic algorithm optimization method for arranging the order of receiving and delivering the postal items and develop a method to decrease the distance between request points. By using this algorithm, the total length of postal vehicles decreased from 720 km to 551 km which is equivalent to 24% savings.
For instance, the second truck's way can be checked to investigate the proposed model's performance. Since can be observed, the algorithm has put the pick-up and delivery points together properly to stop the truck from driving around the study area. It can similarly be recognized that the truck's movement numbers are adjacent to each other. It means that the delivery points are ordered to follow each other, and the postal vehicle evades moving significant ways. Consequently, the vehicle's driving length is decreased, which decreases the overall driving length of all vehicles. Nevertheless, the first vehicle's route does not look so visually optimal. It can be seen that the vehicle has been required to move to some distant points. First, the ultimate solution's fitness function's state holds the lowest possible value among the solutions. Furthermore, the algorithm could not optimize the paths more, and it has to insert some distant locations in the route of one of the vehicles. Indeed, every attempt has been performed to gain the most suitable paths. However, we can optimize this problem by improving our methods or use other metaheuristics algorithms for future research. |
Article number: 7 |
| Keywords: Pickup and delivery of postal items, optimization, genetic algorithm, urban transportation. |
|
|
Full-Text [PDF 1272 kb]
(274 Downloads)
|
Type of Study: Tarviji |
Subject:
GIS
Received: 2021/04/15
|
|
|
|
|
|
|
| References |
|
1. Beasley, D., Bull, D. R., & Martin, R. R. (1993). An overview of genetic algorithms: Part 1, fundamentals. University computing, 15(2), 56-69. 2. Benavent, E., Landete, M., Mota, E., & Tirado, G. (2015). The multiple vehicle pickup and delivery problem with LIFO constraints. European Journal of Operational Research, 243(3), 752-762. [ DOI:10.1016/j.ejor.2014.12.029] 3. Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410. [ DOI:10.1287/opre.2.4.393] 4. Dantzig, G. B., & Fulkerson, D. R. (1954). Minimizing the number of tankers to meet a fixed schedule. Naval Research Logistics Quarterly, 1(3), 217-222. [ DOI:10.1002/nav.3800010309] 5. Davoodi, M., Malekpour Golsefidi, M., & Mesgari, M. S. (2019). A HYBRID OPTIMIZATION METHOD FOR VEHICLE ROUTING PROBLEM USING ARTIFICIAL BEE COLONY AND GENETIC ALGORITHM. International Archives of the Photogrammetry, Remote Sensing & Spatial Information Sciences. [ DOI:10.5194/isprs-archives-XLII-4-W18-293-2019] 6. D'Souza, C., Omkar, S. N., & Senthilnath, J. (2012). Pickup and delivery problem using metaheuristics techniques. Expert Systems with Applications, 39(1), 328-334. [ DOI:10.1016/j.eswa.2011.07.022] 7. Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483. [ DOI:10.1016/j.cie.2009.05.009] 8. Fan, J. (2011). The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. Procedia Engineering, 15, 5284-5289. [ DOI:10.1016/j.proeng.2011.08.979] 9. Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53. [ DOI:10.1016/j.cie.2012.01.005] 10. Golberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addion wesley, 1989(102), 36. 11. Grimault, A., Bostel, N., & Lehuédé, F. (2017). An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization. Computers & Operations Research, 88, 1-14. [ DOI:10.1016/j.cor.2017.06.012] 12. Mao-xiang, L. A. N. G. (2005). Study on simulated annealing algorithm for vehicle routing problem with backhauls [J]. Journal of systems engineering, 5. 13. Masson, R., Lehuédé, F., & Péton, O. (2013). An adaptive large neighborhood search for the pickup and delivery problem with transfers. Transportation Science, 47(3), 344-355. [ DOI:10.1287/trsc.1120.0432] 14. Naccache, S., Côté, J. F., & Coelho, L. C. (2018). The multi-pickup and delivery problem with time windows. European Journal of Operational Research, 269(1), 353-362. [ DOI:10.1016/j.ejor.2018.01.035] 15. Sivanandam, S. N., & Deepa, S. N. (2007). Introduction to Genetic Algorithms. Springer, Berlin Heidelberg. 16. Tajik, N., Tavakkoli-Moghaddam, R., Vahdani, B., & Mousavi, S. M. (2014). A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty. Journal of Manufacturing Systems, 33(2), 277-286. [ DOI:10.1016/j.jmsy.2013.12.009] 17. Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics. [ DOI:10.1137/1.9781611973594] 18. Wang, H. F., & Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62(1), 84-95. [ DOI:10.1016/j.cie.2011.08.018] 19. Van Zuylen, H. J., & Willumsen, L. G. (1980). The most likely trip matrix estimated from traffic counts. Transportation Research Part B: Methodological, 14(3), 281-293. [ DOI:10.1016/0191-2615(80)90008-9] |
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
|
|
