PRE2019 3 Group16
Group Members
| Name | Student Number | Study | |
|---|---|---|---|
| Efe Utku | 1284290 | Applied Physics | e.utku@student.tue.nl |
| Roel den Hoet | 1248170 | Computer Science | r.d.hoet@student.tue.nl |
| Venislav Varbanov | 1284401 | Computer Science | v.varbanov@student.tue.nl |
Algorithm notes (Venislav)
Input:
- social network: undirected graph, vertices represent people and have coordinates and condition, edges between people who often communicate
- number of drone bases, coordinates of each base, number of drones per base
- range, flight time(entire day?, or add recharge time), speed and capacity of drones
Output/score: total number of people that got sick and/or time until no more people could get sick
Two ways we can choose which people get sick:
1. People that got sick the previous day or earlier and are not yet diagnosed have a chance x of transmitting the disease to each neighbor. A person with n sick undiagnosed neighbors has chance of getting sick min(100%,n*x). (preferred by me)
2. Use provided formula to compute x - the increase of sick people in a day, and pick x random people with a sick undiagnosed neighbor (if there are enough such people) and make them sick.
Day 1: Initially some people are sick (P). They get some of their neighbors (N) sick (S) and their connections are removed. Each of N picks a time window from 08:00 to 00:00 the same day. The drones try to cover as many of N as possible (D).
Day 2: Until 08:00 results of D are ready and connections of identified sick people are removed. People of S-D get some of their neighbors sick (S’). We consider all neighbors (N’) of N-D. Each of N-D and N’ picks a time window from 08:00 to 00:00 the same day. The drones try to cover as many of N-D and N’ as possible (D’).
Day 3: Until 08:00 results of D’ are ready and connections of identified sick people are removed. People of S-D-D’ and S’-D’ get some of their neighbors sick (S’). People of S-D-D’ self-diagnose and remove their connections. Let M be the neighbors of S-D-D’. We consider all neighbors (N’’) of M-D’. Each of M-D’ and N’’ picks a time window from 08:00 to 00:00 the same day. The drones try to cover as many of M-D’ and N’’ as possible (D’’).
…
Problem Statement
Infectious disease outbreaks are a fundamental problem of humans. There are various settings worldwide that might lead to an epidemic or a pandemic. Although these outbreaks have significant impacts on the society; one of them is the economical results of it. Here, we suggest a drone operation responsible for collecting and testing nasopharyngeal specimen from people living in preselected disease-prone regions and communities. By keeping a precise track of more people in less time compared to currently used strategies; we aim to decrease the effects of the outbreak on the community and to evaluate our results in terms of the economic impact of the strategy.
Subject
Epidemics are defined as local infectious disease outbreaks that occur in a community or region. These outbreaks have major impacts on the daily life of community members as economical, social and political issues. The economical problems are mostly due to measures taken to prevent the spreading of the disease; e.g. working, transportation and gatherings in public areas are halted. To minimize these impacts one must keep an up-to-date record of regions that are prone, people who might be infected and people who are more susceptible to infections; because in the bigger picture the main problem is to identify and track reported cases. Only this way, the spreading can be reduced and the distribution of new cases per day can be minimized.
An efficient way to do this is to detect the “local source” of an outbreak and reinvestigate the timeline of the spread. However, this approach also has cost and logistic complications within, depending on the number of cases and days passed since the identification outbreak. So, we suggest an alternative way to keep an outbreak under control; which is to use an aerial drone-based operation for specimen collection and accurate case identification.
The core aim of the drone operations is to provide a faster logistic solution for case reporting; hence, providing a faster tactic to act and take precautions regarding the spread. This subject is going to be investigated in terms of its’ effects on different stakeholders and the its’ numerical impact on the way the disease spreads. The later, technical, part also consists of 2 components. First one is the mathematical model describing the population dynamics with and without the drone strategy, and the second one is an optimization problem to get a realistic point of view on the costs and possibilities of this strategy. Then, by combining these two technical components a feasibility study will be conducted to compare the total cost/ economical impact of the outbreak on the community and the total cost of the drone operations. The economic impact is going to be calculated based on GDP per capita per day and the duration of the epidemic without the drone operations. The cost of the drone operations is going to be calculated based on the cost of a single drone, number of drones operating, duration of the epidemic with the drone operations and other logistic costs.
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 to be used by self-driving delivery cars can be divided into:
- Primary user: Delivery companies that will use fewer vehicles and will use less fuel/energy and thus make more profit by delivering in a more efficient way.
- Primary user: The customer that will receive his order within the time window he has chosen.
- Primary user: Manufacturers that produce the product to be delivered that will be picked up within their opening hours.
- 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 3: Make plan - research algorithm and model
Week 4: Research algorithm and drone - create model
Week 5: Implement algorithm - research drone
Week 6: Simulate algorithm - research drone
Week 7: Create presentation
Week 8: Give presentation
Milestones
Week 3: New subject chosen - plan made
Week 4: Research of algorithm done - model done
Week 5: Algorithm implemented and tested - drone research done
Week 6: Case example simulated - drone component list done
Week 7: Wiki finalized
Week 8: Presentation finalized
Deliverables
Network and mathematical model of the disease
Optimization of drone fleet and operation base location
Simulation of case example
Basic model for drone including component list, applicable models and cost list
Who will do what
Zakaria Ameziane - Work on wiki page, research on algorithms
Cahitcan Uzman - Work on wiki page, research on algorithms
Efe Utku - Work on wiki page, research on algorithms
Roel den Hoet - Research of algorithms, implementation and testing of algorithms
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: