정시배송가능 시간대(time window) 제시를 위한 다중정류소(multi-depot) 다회전(multi-trip) 차량경로문제: 온라인 할당 및 오프라인 재할당 접근법
Multi-depot Multi-trip Vehicle Routing Problem for Offering Available Delivery Time Windows: Online Assignment and Offline Reassignment Approach
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
.
Abstract
The last mile delivery efficiency is becoming prominent, as its demand is boosting. As the last mile delivery provider and customer are both interested in differentiated services, on-demand delivery and time-reserved delivery services are receiving attention. This research characterizes the problem into multi-depot multi-trip vehicle routing problem for offering available delivery time windows (MD&T VRPOTW). A mathematical formulation for the problem that includes previous schedule constraints and current-time constraints is provided. A strategy for reducing complexity is suggested. The problems were solved using CPLEX, and the complexity reduction was proven effective in online assignments. The experiments on offline re-assignment showed that over 10% of delivery distance (time) can be reduced when the schedules were re-assigned or re-optimized after about 10 delivery scheduled had been accumulated. This research and directed future research should contribute to the improvement of on-demand delivery and time-reserved delivery services.
참고문헌 (41)
- AbdAllah, A. M. F. M., "On solving periodic re-optimization dynamic vehicle routing problems", Applied Soft Computing Journal, 55, pp.1~12 (2017)[DOI]
- Alonso-Mora, J., "On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment", Proceedings of the National Academy of Sciences of the United States of America, 114(3), pp.462~467 (2017)[DOI]
- Baldacci, R., "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints", European Journal of Operational Research, 218(1), pp.1~6 (2012)[DOI]
- Bhatti, A., "Ecommerce Trends During Covid-19", International Journal of Future Generation Communication and Networking, pp.1~25 (2020)
- Boysen, N., "Last-mile delivery concepts : a survey from an operational research perspective", OR Spectrum, 43(1), pp.1~58 (2021)[DOI]
- Dablanc, L., "The rise of on-demand ‘Instant Deliveries’ in European cities", Supply Chain Forum, 18(4), pp.203~217 (2017)[DOI]
- Dalmeijer, K., "A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem", Computers and Operations Research, 89, pp.140~152 (2018)[DOI]
- Desrochers, M., "Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints", Operations Research Letters, 10(1), pp.27~36 (1991)[DOI]
- Dixit, A., "Vehicle routing problem with time windows using meta-heuristic algorithms: A survey. Advances in Intelligent Systems and Computing (Vol. 741)" (2019), Springer Singapore
- El-Sherbeny, N. A., "Vehicle routing with time windows : An overview of exact, heuristic and metaheuristic methods", Journal of King Saud University-Science, 22(3), pp.123~131 (2010)[DOI]
- "Distance Matrix API"[URL]
- "Graphopper Routing Engine" (2022)[URL]
- Jahanshahi, H., "A deep reinforcement learning approach for the meal delivery problem", Knowledge-Based Systems, 243, pp.108489~ (2022)[DOI]
- "GS Shop, expected arrival date service “Delivery on customer’s preferred date”" (2022)[URL]
- Korea Maritime Institute, "Korea Maritime Institute International Logistics Weekly (Vol. 625)", ~ (2022)
- Kucharska, E, "Dynamic Vehicle Routing Problem—Predictive and Unexpected Customer Availability", Symmetry (2019)[DOI]
- "“Eliminate delivery costs and reduce the minimum order amount” Competition for immediate delivery initiative in full swing" (2022)[URL]
- Li, J., "Meal delivery routing optimization with order allocation strategy based on transfer stations for instant logistics services", IET Intelligent Transport Systems, pp.1108~1126 (2022)[DOI]
- Li, S., "Trip-Vehicle Assignment Algorithms for Ride-Sharing. Combinatorial Optimization and Applications", LNCS, 12577, pp.685~700 (2020)[DOI]
- "Homeplus Express with “Immediate Delivery in 1 Hour”" (2021)[URL]
- "Global Ecommerce Growth Forecast 2022" (2022)[URL]
- Mori, J. C. M., "On the Request-Trip-Vehicle Assignment Problem", SIAMConference on Applied and Computational Discrete Algorithms(ACDA21), 693, pp.228~239 (2021)
- "Maps Application Services - NAVER Cloud Platform"[URL]
- Neves-Moreira, F., "The time window assignment vehicle routing problem with product dependent deliveries", Transportation Research Part E: Logistics and Transportation Review, 116, pp.163~183 (2018)[DOI]
- Ojeda Rios, B. H., "Recent dynamic vehicle routing problems : A survey", Computers and Industrial Engineering, 160 (2021)[DOI]
- "Openrouteservice: The open source route planner api" (2022)[URL]
- "Setting up a local copy of the OpenStreetMap database" (2015)[URL]
- "Open Source Routing Machine: High performance routing engine run on OpenStreetMap data" (2021)[URL]
- Park, H., "The Changes in the Parcel delivery service according to the Spread of COVID-19 in Korea", Journal of Transport Research, 28(2), pp.51~66 (2021)[DOI]
- Pillac, V., "A review of dynamic vehicle routing problems", European Journal of Operational Research, 225(1), pp.1~11 (2013)[DOI]
- "The Meal Delivery Routing Problem" (2018)[URL]
- "T Direct Shop, arrive at your desired time and place"[URL]
- "TMAP API"[URL]
- Spliet, R., "The discrete time window assignment vehicle routing problem", European Journal of Operational Research, 244(2), pp.379~391 (2015)[DOI]
- Spliet, R., "The Time Window Assignment Vehicle Routing Problem", Transportation Science, 49(4), pp.721~731 (2015)[DOI]
- "Ride with Uber - Request Rides 24/7" (2020)[URL]
- Ulmer, M. W., "The restaurant meal delivery problem : Dynamic pickup and delivery with deadlines and random ready times", Transportation Science, 55(1), pp.75~100 (2021)[DOI]
- "Valhalla: Open Source Routing Engine for OpenStreetMap" (2021)[URL]
- Wang, X., "An XGBoost-enhanced fast constructive algorithm for food delivery route planning problem", Computers and Industrial Engineering, 152, pp.107029~ (2020)[DOI]
- Zhao, K., "Online vehicle dispatch: From assignment to scheduling", IEEE International Conference on Data Mining Workshops, pp.608~611 (2019), ICDMW
- Zhou, Z., "A scalable vehicle assignment and routing strategy for real-time on-demand ridesharing considering endogenous congestion", Transportation Research Part C: Emerging Technologies, 139 (2022)[DOI]
