臺灣博碩士論文加值系統

This research proposes a new variant of two-echelon vehicle routing problem called the two-echelon vehicle routing problem in city logistics (2E-VRPCL). The problem considers two levels of freight distribution network where customers are located at the second echelon while their goods are transported to various intermediate facilities from the source of goods in the first echelon. Customers can receive their goods at their homes or are assigned to perform self-pickup at the nearest alternative pick-up points. Two types of fleets, city freighters and occasional drivers, are available to deliver goods to customers’ homes. In order to enhance the utilization of occasional drivers, alternative intermediate facilities called transshipment nodes are considered in the problem. The objective of 2E-VRPCL is to minimize the total operational cost. We cast the problem into a mixed integer linear programming model and devise a hybrid adaptive large neighborhood search (HALNS) using, amongst others, set-partitioning like neighborhoods, to provide solutions for newly generated 2E-VRPCL instances. Extensive experiments show that a high-quality performance of HALNS for solving two special cases of 2E-VRPCL. Besides, we improve 24 best-known solutions for one of the special cases. Our experimental results confirm that the system in 2E-VRPCL becomes more beneficial under several circumstances, i.e., wider time windows of occasional drivers and customers, higher capacity values of covering locations, and higher capacity values of transshipment nodes. Higher capacity values of transshipment nodes also result in higher utilization of ODs while lower capacity values require the system to use more city freighters.

This research proposes a new variant of two-echelon vehicle routing problem called the two-echelon vehicle routing problem in city logistics (2E-VRPCL). The problem considers two levels of freight distribution network where customers are located at the second echelon while their goods are transported to various intermediate facilities from the source of goods in the first echelon. Customers can receive their goods at their homes or are assigned to perform self-pickup at the nearest alternative pick-up points. Two types of fleets, city freighters and occasional drivers, are available to deliver goods to customers’ homes. In order to enhance the utilization of occasional drivers, alternative intermediate facilities called transshipment nodes are considered in the problem. The objective of 2E-VRPCL is to minimize the total operational cost. We cast the problem into a mixed integer linear programming model and devise a hybrid adaptive large neighborhood search (HALNS) using, amongst others, set-partitioning like neighborhoods, to provide solutions for newly generated 2E-VRPCL instances. Extensive experiments show that a high-quality performance of HALNS for solving two special cases of 2E-VRPCL. Besides, we improve 24 best-known solutions for one of the special cases. Our experimental results confirm that the system in 2E-VRPCL becomes more beneficial under several circumstances, i.e., wider time windows of occasional drivers and customers, higher capacity values of covering locations, and higher capacity values of transshipment nodes. Higher capacity values of transshipment nodes also result in higher utilization of ODs while lower capacity values require the system to use more city freighters.

ABSTRACT i
ACKNOWLEDGEMENTS iii
TABLE OF CONTENTS iv
LIST OF TABLES vi
LIST OF FIGURES vii
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Research objective and contribution 4
1.3 Scope and limitations 5
1.4 Organization of thesis 6
CHAPTER 2 LITERATURE REVIEW 8
2.1 Crowd-Shipping 8
2.2 Parcel Lockers 10
2.3 Two-Echelon Vehicle Routing Problems 11
CHAPTER 3 MODEL DEVELOPMENT 14
3.1 Problem Definition 14
3.2 Mixed Integer Linear Programming Model 21
CHAPTER 4 SOLUTION METHODOLOGY 27
4.1 Hybrid adaptive large neighborhood search 27
4.2 The general outline of HALNS 29
4.3 Destroy operators 31
4.4 Repair operators 34
4.5 Local search 35
4.6 Set partitioning formulation 38
CHAPTER 5 COMPUTATIONAL RESULTS 43
5.1 Description of the benchmark instances 43
5.2 Parameter setting for the HALNS 45
5.3 HALNS performance for solving 2E-VRP and 2E-VRPTW-CO-OD benchmark instances 47
5.4 HALNS performance for solving 2E-VRPCL benchmark instances 51
5.5 Effectiveness of VND and SPP for solving 2E-VRPCL 54
5.6 Sensitivity analyses 57
CHAPTER 6 CONCLUSION AND FUTURE RESEARCH 66
6.1. Conclusion 66
6.2. Future Research 67
REFERENCES 68
APPENDIX 76

Akpunar, Ö. Ş., & Akpinar, Ş. (2021). A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem. Expert Systems with Applications, 168, 114304.
Anderluh, A., Nolz, P. C., Hemmelmayr, V. C., & Crainic, T. G. (2021). Multi-objective optimization of a two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’customers arising in urban logistics. European Journal of Operational Research, 289(3), 940-958.
Archetti, C., & Bertazzi, L. (2021). Recent challenges in Routing and Inventory Routing: E‐commerce and last‐mile delivery. Networks, 77(2), 255-268.
Archetti, C., Guerriero, F., & Macrina, G. (2021). The online vehicle routing problem with occasional drivers. Computers & Operations Research, 127, 105144.
Archetti, C., Savelsbergh, M., & Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480.
Archetti, C., & Speranza, M. G. (2014). A survey on matheuristics for routing problems. EURO Journal on Computational Optimization, 2(4), 223-246.
Boysen, N., Fedtke, S., & Schwerdfeger, S. (2021). Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum, 43(1), 1-58.
Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science, 39(1), 104-118.
Breunig, U., Schmid, V., Hartl, R. F., & Vidal, T. (2016). A large neighbourhood based heuristic for two-echelon routing problems. Computers & Operations Research, 76, 208-225.
Crainic, T. G., Perboli, G., Mancini, S., & Tadei, R. (2010). Two-echelon vehicle routing problem: a satellite location analysis. Procedia-Social and Behavioral Sciences, 2(3), 5944-5955.
Dahle, L., Andersson, H., Christiansen, M., & Speranza, M. G. (2019). The pickup and delivery problem with time windows and occasional drivers. Computers & Operations Research, 109, 122-133.
Dellaert, N., Dashty Saridarq, F., Van Woensel, T., & Crainic, T. G. (2019). Branch-and-price–based algorithms for the two-echelon vehicle routing problem with time windows. Transportation Science, 53(2), 463-479.
Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2), 346-359.
Deutsch, Y., & Golany, B. (2018). A parcel locker network as a solution to the logistics last mile problem. International Journal of Production Research, 56(1-2), 251-261.
Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2), 283-308.
Enthoven, D. L., Jargalsaikhan, B., Roodbergen, K. J., uit het Broek, M. A., & Schrotenboer, A. H. (2020). The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers. Computers & Operations Research, 118, 104919.
Foster, B. A., & Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society, 27(2), 367-384.
Geissinger, A., Laurell, C., Öberg, C., & Sandström, C. (2019). How sustainable is the sharing economy? On the sustainability connotations of sharing economy platforms. Journal of Cleaner Production, 206, 419-429.
Grabenschweiger, J., Doerner, K. F., Hartl, R. F., & Savelsbergh, M. W. (2021). The vehicle routing problem with heterogeneous locker boxes. Central European Journal of Operations Research, 29(1), 113-142.
Grangier, P., Gendreau, M., Lehuédé, F., & Rousseau, L.-M. (2017). A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. Computers & Operations Research, 84, 116-126.
Gschwind, T., & Drexl, M. (2019). Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transportation Science, 53(2), 480-491.
Hammami, F., Rekik, M., & Coelho, L. C. (2019). Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet. Transportation Research Part E: Logistics and Transportation Review, 127, 150-177.
Hammami, F., Rekik, M., & Coelho, L. C. (2020). A hybrid adaptive large neighborhood search heuristic for the team orienteering problem. Computers & Operations Research, 123, 105034.
Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
Jiang, L., Dhiaf, M., Dong, J., Liang, C., & Zhao, S. (2020). A traveling salesman problem with time windows for the last mile delivery in online shopping. International Journal of Production Research, 58(16), 5077-5088.
Kafle, N., Zou, B., & Lin, J. (2017). Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery. Transportation Research Part B: Methodological, 99, 62-82.
Le Colleter, T., Dumez, D., Lehuédé, F., & Péton, O. (2022). Small and Large Neighborhood Search for the Park-and-Loop Routing Problem with Parking Selection. hal-03631730.
Le, T. V., Stathopoulos, A., Van Woensel, T., & Ukkusuri, S. V. (2019). Supply, demand, operations, and management of crowd-shipping services: A review and empirical evidence. Transportation Research Part C: Emerging Technologies, 103, 83-103.
Le, T. V., Ukkusuri, S. V., Xue, J., & Van Woensel, T. (2021). Designing pricing and compensation schemes by integrating matching and routing models for crowd-shipping systems. Transportation Research Part E: Logistics and Transportation Review, 149, 102209.
Li, H., Liu, Y., Chen, K., & Lin, Q. (2020). The two-echelon city logistics system with on-street satellites. Computers & Industrial Engineering, 139, 105577.
Lin, Y. H., Wang, Y., He, D., & Lee, L. H. (2020). Last-mile delivery: Optimal locker location under multinomial logit choice model. Transportation Research Part E: Logistics and Transportation Review, 142, 102059.
Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laganà, D. (2017). The vehicle routing problem with occasional drivers and time windows. International conference on optimization and decision science (pp. 577-587). 4-7 September. Sorrento, Italy.
Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laporte, G. (2020). Crowd-shipping with time windows and transshipment nodes. Computers & Operations Research, 113, 104806.
Mancini, S. (2017). A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times. Computers & Operations Research, 88, 290-296.
Mancini, S., & Gansterer, M. (2021). Vehicle routing with private and shared delivery locations. Computers & Operations Research, 133, 105361.
Mancini, S., & Gansterer, M. (2022). Bundle generation for last-mile delivery with occasional drivers. Omega, 108, 102582.
Marques, G., Sadykov, R., Deschamps, J.-C., & Dupas, R. (2020). An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Computers & Operations Research, 114, 104833.
Moncef, B., & Dupuy, M. M. (2021). Last-mile logistics in the sharing economy: sustainability paradoxes. International Journal of Physical Distribution & Logistics Management, 51(5), 508-527.
Moore, F., Americo, A., Sarrió, N., & Axinte, L. (2021). Low Emission Zones and Urban Logistics: How can we make it work? Retrieved from https://ulaads.eu/low-emission-zones-and-urban-logistics-how-can-we-make-it-work/. Retrieved at April 1st, 2022.
Mühlbauer, F., & Fontaine, P. (2021). A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles. European Journal of Operational Research, 289(2), 742-757.
Orenstein, I., Raviv, T., & Sadan, E. (2019). Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO Journal on Transportation and Logistics, 8(5), 683-711.
Oyola, J., Arntzen, H., & Woodruff, D. L. (2017). The stochastic vehicle routing problem, a literature review, part II: solution methods. EURO Journal on Transportation and Logistics, 6(4), 349-388.
Oyola, J., Arntzen, H., & Woodruff, D. L. (2018). The stochastic vehicle routing problem, a literature review, part I: models. EURO Journal on Transportation and Logistics, 7(3), 193-221.
Pan, B., Zhang, Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1), 218-231.
Perboli, G., Tadei, R., & Vigo, D. (2011). The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3), 364-380.
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403-2435.
Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1), 1-17.
Rai, H. B., Verlinde, S., Merckx, J., & Macharis, C. (2017). Crowd logistics: an opportunity for more sustainable urban freight transport? European Transport Research Review, 9(3), 1-13.
Reed, S., Campbell, A. M., & Thomas, B. W. (2021). Does parking matter? The impact of search time for parking on last-mile delivery optimization. arXiv preprint arXiv:2107.06788.
Ropke, S., & Pisinger, D. (2006a). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455-472.
Ropke, S., & Pisinger, D. (2006b). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750-775.
Savelsbergh, M., & Van Woensel, T. (2016). 50th anniversary invited article—city logistics: Challenges and opportunities. Transportation Science, 50(2), 579-590.
Savelsbergh, M. W., & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29(1), 17-29.
Schrotenboer, A. H., Broek, M. A., Buijs, P., & Ulmer, M. W. (2021). Fighting the e-commerce giants: efficient routing and effective consolidation for local delivery platforms. arXiv preprint arXiv:2108.12608.
Schrotenboer, A. H., uit het Broek, M. A., Jargalsaikhan, B., & Roodbergen, K. J. (2018). Coordinating technician allocation and maintenance routing for offshore wind farms. Computers & Operations Research, 98, 185-197.
Sitek, P., & Wikarek, J. (2019). Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach. Annals of Operations Research, 273(1), 257-277.
Torres, F., Gendreau, M., & Rei, W. (2022). Crowd-Shipping: Determining the Compensation of Crowd-Drivers with Stochastic Route Acceptance. CIRRELT.
Toth, P., & Vigo, D. (2002). The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia.
Turkeš, R., Sörensen, K., & Hvattum, L. M. (2021). Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search. European Journal of Operational Research, 292(2), 423-442.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1-21.
Wang, K., Shao, Y., & Zhou, W. (2017). Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service. Transportation Research Part D: Transport and Environment, 57, 262-276.
Yildiz, B., & Savelsbergh, M. (2019). Service and capacity planning in crowd-sourced delivery. Transportation Research Part C: Emerging Technologies, 100, 177-199.
Yu, V. F., Jodiawan, P., Hou, M.-L., & Gunawan, A. (2021). Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers. Transportation Research Part E: Logistics and Transportation Review, 154, 102461.
Yu, V. F., Lin, S.-W., & Gunawan, A. (2020). Design of a two-echelon freight distribution system in an urban area considering third-party logistics and loading–unloading zones. Applied Soft Computing, 97, 106707.
Yu, Y., Lian, F., & Yang, Z. (2021). Pricing of parcel locker service in urban logistics by a TSP model of last-mile delivery. Transport Policy, 114, 206-214.
Zhang, Y., Sun, L., Hu, X., & Zhao, C. (2019). Order consolidation for the last-mile split delivery in online retailing. Transportation Research Part E: Logistics and Transportation Review, 122, 309-327.
Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265(2), 765-778.