Optimization for Logistic Tasks
1. Short Description
Logistics is one of the most important services for any industry and society. It the questions of how to best get objects from A to B. In China’s Logistics Industry Development Report 2013-2014, the total social logistics cost were given as 197.8 trillion RMB, accounting for 18 percent of the total GDP. Many questions in logistics are optimization problems: How can we visit a set of cities while travelling the overall minimum distance? How can we deliver a set of goods to a set of customers with capacity-limited vehicles at minimal costs? Considering such tasks from the optimization perspective can yield huge reductions in terms of costs, resource consumption, man power, and even pollution.
For several years, researchers at UBRI significantly contribute to that field. These contributions can be categorized into different problem domains as follows.
1.1. Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is one of the oldest logistic planning tasks. Here, a salesperson starts in a given city, wants to visit n other cities, and return back to her or his origin. The overall traveling distance should be minimized.
Based on our prior research on developmental mappings, an approach to deal with large-scale problems, URBI researchers have created a developmental algorithm for the TSP based on Genetic Programming. This project is also the origin of our TSPSuite project, which aims at developing better experimental methodologies to compare optimization methods (on the example of the TSP) and has resulted in a fully-fledged implementation of a benchmark, experimentation, and evaluation environment.
Using this environment, we have investigated the performance of several well-known algorithms, such as Evolutionary Algorithms, Ant Colony Optimization algorithms, Estimation of Distribution Algorithms, local search methods such as Variable Neighborhood Search, and their hybrids. This has not only led to the confirmation of known and finding of new issues, but also to the development of novel approaches (such as hybrid Branch-and-Bound methods) for the TSP.
1.2. Capacitated Arc Routing Problem
In the Capacitated Arc Routing Problem (CARP), the goal is to distribute certain goods to roads on the map (not singular locations) with capacity-limited vehicles. One of the best algorithms for this domain, MAENS, has been developed at UBRI.
1.3. Vehicle Routing Problems with Time Windows
Vehicle Routing Problems with Time Windows (VRPTWs) are problems where goods need to be delivered to customers from a central depot. These deliveries are bound to time windows, i.e., if a vehicle comes too late, the customer gets angry. If it comes too early, it needs to wait. Additionally, vehicles are limited in capacity. The goal is to use as few vehicles as possible to satisfy all customers. These vehicles should, additionally, travel the overall shortest distance.
At UBRI, we conduct research on Ant Colony Optimization algorithms for this purpose, which are enhanced with intelligent initialization procedures and hybridized with local search.
2. Involved Researchers
- Prof. Dr. Ke Tang [唐轲]
- Dr. Thomas Weise, Assoc. Prof.
- Shi Wei [施玮], MSc. Student
- Liu Weichen [刘伟臣], MSc. Student
- Yan Jiang [江炎], MSc. Student
- Yuezhong Wu [吴越钟], MSc. Student
- Jin Ouyang [欧阳晋], Alumni R.A.
- Dr. Yi Mei [梅一], Almuni PhD. Student
- Haobo Fu, Almuni MsC Student
- "A Framework for Next Generation Algorithm Benchmarking: Performance Testing and Community Building", Funding Body: The University of Newcastle (UoN), Callaghan, NSW, Australia, Duration: 2014
- "Intelligent Transportation Planning: Benchmarking of Novel Business Analytics Techniques using the Travelling Salesman Problem as a Test-Bed", Funding Body: The University of Newcastle (UoN), Callaghan, NSW, Australia, Grant Type: Faculty Strategic Initiatives Research Fund (SIRF) Grant, Duration: 2013
4. Resulting Publications
4.1. Refereed Journal Articles
- Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine (CIM), 9(3):40-52, August 2014.
- Y. Mei, K. Tang and X. Yao, "A Memetic Algorithm for Periodic Capacitated Arc Routing Problem," IEEE Transactions on Systems, Man, and Cybernetics: Part B, 41(6): 1654-1667, December, 2011.
- Ke Tang, Yi Mei and Xin Yao: "Memetic Algorithm with Extended Neighborhood Search for Capacitated Arc Routing Problems", IEEE Transactions on Evolutionary Computation, 13(5):1151-1166, October 2009.
Available as a PDF here.
- Yi Mei, Ke Tang and Xin Yao: "A Global Repair Operator for Capacitated Arc Routing Problem", IEEE Transactions on Systems, Man, and Cybernetics: Part B, 39(3):723-734, June 2009.
Available as a PDF here.
4.2. Refereed Conference Papers
- Yan Jiang, Thomas Weise, Jörg Lässig, Raymond Chiong, and Rukshan Athauda. "Comparing a Hybrid Branch and Bound Algorithm with Evolutionary Computation Methods, Local Search and their Hybrids on the TSP". In Proceedings of the IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS’14), Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI’14), Orlando, FL, USA: Caribe Royale All-Suite Hotel and Convention Center, December 9–12, 2014. Los Alamitos, CA, USA: IEEE Computer Society Press.
- J. Ouyang, T. Weise, A. Devert, and R. Chiong: "SDGP: A Developmental Approach for Traveling Salesman Problems," in Proceedings of the 2013 IEEE Symposium Series on Computational Intelligence (SSCI). Singapore, April 15-19, 2013.
- T. Weise, K. Tang and A. Devert: "A Developmental Solution to (Dynamic) Capacitated Arc Routing Problems using Genetic Programming," in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'12), Philadelphia, PA, USA, July 7–11, 2012, pp. 831-838.
- Wei Shi and Thomas Weise. "An Initialized ACO for the VRPTW." In Hujun Yin, Ke Tang, Yang Gao, Frank Klawonn, Minho Lee, Thomas Weise, Bin Li, and Xin Yao, editors, Proceedings of the 14th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL’13), volume 8206/2013 of Lecture Notes in Computer Science (LNCS), pages 93-100, Hefei, Anhui, China: Empark Grand Hotel, October 20–23, 2013. Berlin, Germany: Springer-Verlag GmbH.
- Y. Mei, K. Tang and X. Yao: "Capacitated Arc Routing Problem in Uncertain Environments,"in Proceedings ofthe 2010 IEEE Congress on Evolutionary Computation (CEC2010), Barcelona, Spain, 18-23 July 2010, pp. 1400-1407.
- H. Fu, Y. Mei, K. Tang and Y. Zhu: "Memetic Algorithm with Heuristic Candidate List Strategy for Capacitated Arc Routing Problem," in Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC2010), Barcelona, Spain, 18-23 July 2010, pp. 3229-3236.
- Yi Mei, Ke Tang and Xin Yao: "Improved Memetic Algorithm for Capacitated Arc Routing Problem", in Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC2009), Norway, 18th-21st May, 2009, pp.1699-1706.
4.3. Book Chapters
- T. Weise, A. Podlich and C. Gorldt, "Solving Real-World Vehicle Routing Problems with Evolutionary Algorithms", in Natural Intelligence for Scheduling, Planning and Packing Problems, Chiong, Raymond and Dhakal, Sandeep (Eds), vol. 250 of Studies in Computational Intelligence (SCI), ISBN: 978-3-642-04038-2, 2010. Available as a PDF here.
- Raymond Chiong from the Applied Informatics Research (AIR) group at the University of Newcastle (UoN)
- Prof. Jörg Lässig from the Enterprise Application Development Group (EAD) of the University of Applied Sciences of Zittau/Görlitz (HSZG)