PRE2019 3 Group16
Group Members
| Name | Student Number | Study | |
|---|---|---|---|
| Zakaria Ameziane | 1005559 | Computer Science | z.ameziane@student.tue.nl |
| Cahitcan Uzman | 1284304 | Computer Science | c.uzman@student.tue.nl |
| Efe Utku | |||
| Roel den Hoet | 1248170 | Computer Science | r.d.hoet@student.tue.nl |
| Venislav Varbanov | 1284401 | Computer Science | v.varbanov@student.tue.nl |
Subject
What/How (AI) algorithms can be used by future self driving delivery cars to efficiently solve the pickup-and-delivery problem with time-windows, where a fleet of delivery vehicles must collect and deliver items according to the demand of customers and their opening hours. The objectives are to minimize the fleet size and to assign a sequence of customers to each truck of the fleet minimizing the total distance traveled.
Objectives
The objective of our project is to find out which (AI) algorithms can be used to optimize the planning of self-driving delivery cars and how. We will work with instances of the pickup-and-delivery problem with time-windows, where a fleet of delivery vehicles must collect and deliver items according to the demand of customers and their opening hours. The objectives are to minimize the fleet size and then to assign a sequence of customers to each vehicle of the fleet minimizing the total distance travelled. We aim to get comparable results with the Li & Lim benchmark for at least the smallest instances of the problem.
Users
The users that will benefit from those algorithms used by self driving delivery cars can be divided into:
- Primary user: Delivery companies that will use less vehicles and make more profit by delivering in a more efficient way.
- Primary user: The customer that will receive his order.
- Secondary user: Other road users that are indirectly influenced, as the number of delivery cars will be reduced, and replaced by self-driving cars that are safer.
Approach
We will first research all papers of people that have beaten a record in the Li & Lim benchmark, then we will research other papers related to algorithms for this or similar problems. We will come up with ideas for achievable (within the length of the project) algorithms based on the read papers which we think would lead to best results. We will then implement and test these algorithms on all problem instances from the Li & Lim benchmark and compare them with the current world records. Finally, we will discuss what we have learned for the problem and the possible algorithmic approaches.
Planning
Week 1: Choosing a subject
Week 2: Planning subject, objectives, users, state-of-the-art, approach, planning, milestones, deliverables, who will do what
Week 3: Research of algorithms | Wiki: finalize subject; finalize objectives; introduction; state-of-the-art
Week 4: Research of algorithms | Implementation and testing of algorithms | Wiki: users; state-of-the-art
Week 5: Finalize research of algorithms | Implementation and testing of algorithms | Wiki: description of algorithms; finalize users; finalize state-of-the-art
Week 6: Finalize implementation and testing | Wiki: finalize description of algorithms; descriptions of results; discussion; future work
Week 7: Finalize wiki
Week 8: Finishing the final presentation and presenting
Milestones
Week 1: Subject chosen
Week 2: Initial planning finished
Week 3: Main research of algorithms done; Finalized subject and objectives on the wiki page, all other sections started
Week 4: Implementation and testing of algorithm 1
Week 5: Finalized research of algorithms; Implementation and testing of algorithm 2; Finalized users and state of the art on the wiki page
Week 6: Finalized implementation and testing (possibly new algorithm); Finalized description of algorithms and descriptions of results on the wiki page
Week 7: All sections on the wiki page finalized
Week 8: Finishing the final presentation and presenting
Deliverables
1. Implementation of one or more algorithms that work with the Li & Lim benchmark instances and produce valid solutions such that the number of vehicles is minimized and then the total distance is minimized as much as possible.
2. Wiki page that contains all the information about our project including the results of running the algorithm(s) on all instances from the Li & Lim benchmark and a comparison with the current records.
3. Final presentation that will explain our project and results.
Who will do what
Zakaria Ameziane
Cahitcan Uzman
Efe Utku
Roel den Hoet
Venislav Varbanov - Research, implementation, testing and description of algorithms
State of the Art
References (of the work of all people that have managed to beat an existing record):
BBM - Baldacci, Bartolini, and Mingozzi. An Exact Algorithm for the Pickup and Delivery Problem. Operations Research 59(2), pp. 414–426 (2011).
BVH - Bent, R. and Van Hentenryck. P. A Two-Stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows. In Principles and Practice of Constraint Programming (2003).
CLS - Curtois, T., Landa-Silva, D., Qu, Y. and Laesanklang, W., 2018. Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows. EURO Journal on Transportation and Logistics, 7(2), pp.151-192.
CVB - Christiaens J. and Vanden Berghe G. A Fresh Ruin & Recreate Implementation for Capacitated Vehicle Routing Problems. To be submitted.
CVB2 - Christiaens J. and Vanden Berghe G. Preliminary title: Slack Induction by String Removals for Vehicle Routing Problems.
DK - Dirk Koning. Using Column Generation for the Pickup and Delivery Problem with Disturbances, Technical Report, Department of Computer Science, Utrecht University, 2011.
EOE - Eirik Krogen Hagen, EOE Koordinering DA. Exploring infeasible and feasible regions of the PDPTW through penalty based tabu search. Working paper.
EMIF - Evgeny Makarov & Ilya Fiks (swatmobile.io).
H - Keld Helsgaun, Working paper, Roskilde University, Denmark (2016).
K – Richard Kelly: Hybrid Ejection Chains and Adaptive LNS for the PDPTW. Working paper.
Li & Lim - Li H. and A. Lim: A MetaHeuristic for the Pickup and Delivery Problem with Time Windows, In Proceedings of the 13th International Conference on Tools with Artificial Intelligence, Dallas, TX, USA, 2001.
MFS - Evgeny Makarov, Ilya Fiks, Eugene Sorokhtin (swatmobile.io). Unpublished.
NB1 - J. Nalepa and M. Blocho. "Enhanced Guided Ejection Search for the Pickup and Delivery Problem with Time Windows", Intelligent Information and Database Systems: Proc. 8th Asian Conference, ACIIDS 2016, pages 388–398. Springer, Heidelberg, 2016.
Q - Quintiq. http://www.quintiq.com/optimization-world-records.aspx.
R - Ropke S. Heuristic and exact algorithms for vehicle routing problems. (2005) . Ph.D. thesis, Computer Science Department, University of Copenhagen (DIKU), Copenhagen
RC - Ropke S. and J.-F. Cordeau. Branch and cut and price for the pickup and delivery problem with time windows. Transportation Sci. 43(3)267–286 (2009).
RP - S. Ropke & D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, Technical Report, Department of Computer Science, University of Copenhagen, 2004.
SAM::OPT - Hasle G., O. Kloster: Industrial Vehicle Routing Problems. Chapter in Hasle G., K-A Lie, E. Quak (eds): Geometric Modelling, Numerical Simulation, and Optimization. ISBN 978-3-540-68782-5, Springer 2007.
SB - Carlo Sartori, Luciana Buriol. A matheuristic approach to the PDPTW (to be submitted).
SCR - Piotr Sielski (psielski@emapa.pl), Piotr Cybula, Marek Rogalski, Mariusz Kok, Piotr Beling, Andrzej Jaszkiewicz, Przemysław Pełka. Emapa S.A. www.emapa.pl "Development of universal methods of solving advanced VRP problems with the use of machine learning", unpublished research funded by The National Centre for Research and Development, project number: POIR.01.01.01-00-0012/19. "Optimization of advanced VRP problem variants", unpublished. Computing grant 358 funded by Poznan Supercomputing and Networking Center.
Shobb - http://shobb.narod.ru/vrppd.html
TS - TetraSoft A/S: MapBooking Algoritm for Pickup and Delivery Solutions with Time Windows and Capacity restraints.
WM - Ganzhong Luo (luoganzhong@water-mirror.com), Lei Gao (gaolei@water-mirror.com), Zhixin Liu, Yaning Li, Mingxiang Chen, Qichang Chen, Nuoyi Zhu. "New Algorithms for VRPTW & PDPTW", unpublished result of WATERMIRROR AI.
Other references: