Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giải quyết các vấn đề định tuyến với các ràng buộc đồng bộ hóa theo cặp
Tóm tắt
Các ràng buộc đồng bộ hóa theo cặp thường gặp trong lĩnh vực định tuyến và lập lịch cho kỹ thuật viên dịch vụ cũng như trong lĩnh vực chăm sóc di động. Đồng bộ hóa theo cặp đề cập đến các ràng buộc yêu cầu hai kỹ thuật viên hoặc nhân viên chăm sóc tại nhà phải thăm cùng một vị trí vào đúng thời gian như nhau. Chúng tôi xem xét các ràng buộc loại này trong bối cảnh của vấn đề định tuyến xe nổi tiếng với các khoảng thời gian và một bài toán định tuyến và lập lịch kỹ thuật viên dịch vụ tổng quát. Nhiều phương pháp khác nhau để giải quyết vấn đề đồng bộ hóa theo cặp được so sánh và một số cách tích hợp thành phần đồng bộ hóa vào một thuật toán metaheuristic được điều chỉnh cho các vấn đề gốc được phân tích. Khi được áp dụng cho các trường hợp chuẩn từ tài liệu, thuật toán của chúng tôi đạt gần như tất cả các giá trị tối ưu có sẵn và tạo ra một số kết quả tốt nhất mới cho các trường hợp còn lại.
Từ khóa
#đồng bộ hóa theo cặp #định tuyến #lập lịch #thuật toán metaheuristic #kỹ thuật viên dịch vụ #chăm sóc di độngTài liệu tham khảo
Afifi S, Dang D-C, Moukrim A (2016) Heuristic solutions for the vehicle routing problem with time windows and synchronized visits. Optim Lett 10(3):511–525
Andersson H, Duesund JM, Fagerholt K (2011) Ship routing and scheduling with cargo coupling and synchronization constraints. Comput Ind Eng 61(4):1107–1116
Armacost A, Barnhart C, Ware KA (2002) Composite variable formulations for express shipment service network design. Transp Sci 36:1–20
Armacost A, Barnhart C, Ware KA, Wilson AM (2004) UPS optimizes its air network. Interfaces 43:15–25
Bögl M, Doerner KF, Parragh SN (2015) The school bus routing and scheduling problem with transfers. Networks 65(2):180–203
Bredström D, Rönnqvist M (2007) A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. Technical report, Department of Finance and Management Science, Norwegian School of Economics and Business Administration
Bredström D, Rönnqvist M (2008) Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur J Oper Res 191:19–29
Dohn A, Koling E, Clausen J (2009) The manpower allocation problem with time windows and job-teaming constraints: a branch-and-price approach. Comput Oper Res 36:1145–1157
Dohn A, Rasmussen MS, Larsen J (2011) The vehicle routing problem with time windows and temporal dependencies. Networks 58(4):273–289
Drexl M (2012) Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints. Transp Sci 46(3):297–316
El Hachemi N, Gendreau M, Rousseau L-M (2013) A heuristic to solve the synchronized log-truck scheduling problem. Comput Oper Res 40(3):666–673
Eveborn P, Flisberg P, Rönnqvist M (2006) Laps Care—an operational system for staff planning of home care. Eur J Oper Res 171:962–976
Eveborn P, Rönnqvist M, Einarsdottir H, Eklund M, Liden K, Almroth M (2009) Operations research improves quality and efficiency in home care. Interfaces 39:18–34
Hemmelmayr V, Doerner KF, Hartl RF, Rath S (2013) A heuristic solution method for node routing based solid waste collection problems. J Heuristics 19:1–28
Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999) Fleet assignment and crew scheduling with synchronization constraints. Eur J Oper Res 119:75–90
Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Kovacs AA, Parragh SN, Doerner KF, Hartl R (2012) Adaptive large neighborhood search for service technician routing and scheduling problems. J Sched 15:579–600
Li Y, Lim A, Rodrigues B (2005) Manpower allocation with time windows and job-teaming constraints. Nav Res Logist 52:302–311
Mankowska DS, Meisel F, Bierwirth C (2014) The home health care routing and scheduling problem with interdependent services. Health Care Manag Sci 17(1):15–30
Masson R, Lehuede F, Peton O (2014) The dial-a-ride problem with transfers. Comput Oper Res 41:12–23
Perrier N, Langevin A, Amaya C-A (2008) Vehicle routing for urban snow plowing operations. Transp Sci 42:44–56
Prins C (2011) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31:1985–2002
Quttineh N-H, Larsson T, Lundberg K, Holmberg K (2013) Military aircraft mission planning: a generalized vehicle routing model with synchronization and precedence. EURO J Transp Logist 2(1–2):109–127
Reinhardt LB, Clausen T, Pisinger D (2013) Synchronized dial-a-ride transportation of disabled passengers at airports. Eur J Oper Res 225(1):106–117
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40:455–472
Rousseau L-M, Gendreau M, Pesant G (2013) The synchronized dynamic vehicle dispatching problem. INFOR Inf Syst Oper Res 51(2):76–83
Salazar-Aguilar A, Langevin A, Laporte G (2012) Synchronized arc routing for snow plowing operations. Comput Oper Res 39:1432–1440
Savelsbergh MWP (1992) The vehicle routing problem with time windows: minimizing route duration. ORSA J Comput 4:146–154
Schmid V, Doerner KF, Hartl Savelsbergh MWP, Stöcher W (2009) A hybrid solution approach for ready mixed concrete delivery. Transp Sci 43:70–85
Schmid V, Doerner KF, Hartl RF, Salazar-Gonzalez JJ (2010) Hybridization of very large neighborhood search for ready-mixed concrete delivery problems. Comput Oper Res 37:559–574
Schönberger J (2017) Scheduling constraints in dial-a-ride problems with transfers: a metaheuristic approach incorporating a cross-route scheduling procedure with postponement opportunities. Public Transp 9:243–272
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35:254–265
Stålhane M, Andersson H, Christiansen M (2015) A branch-and-price method for a ship routing and scheduling problem with cargo coupling and synchronization constraints. EURO J Transp Logist 4:421–443