• Previous Article
    A novel BWM integrated MABAC decision-making approach to optimize the wear parameter of CrN/TiAlSiN coating
  • JIMO Home
  • This Issue
  • Next Article
    A vendor-managed inventory model based on optimal retailers selection and reliability of supply chain
doi: 10.3934/jimo.2022018
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

The synchronized multi-assignment orienteering problem

University of Mary Washington, College of Business, 1301 College Avenue, Fredericksburg, VA, 22401, USA

Received  November 2021 Revised  February 2022 Early access February 2022

We introduce the Synchronized Multi-Assignment Orienteering Problem (SMOP), a vehicle routing problem that requires jointly selecting a set of jobs while synchronizing the assignment and transportation of agents to roles to form ad-hoc teams at different job locations. Agents must be assigned only to roles for which they are qualified. Each job requires a certain number of agents in each role within a time window and contributes a reward score if selected. The task is to maximize the total reward attained. SMOP can model many real-world scenarios requiring coordinated transportation of resources and accommodates traditional depot-based workforces, depot workforces supplemented by ad-hoc workers, and fully ad-hoc workforces alike. The same problem formulation can be used for initial planning and mid-course replanning. We develop a mixed integer programming formulation (MIP) and an Adaptive Large Neighborhood Search algorithm (ALNS). In computational experiments covering a range of considerations, ALNS consistently found very near-optimal solutions on smaller problems and surpassed a commercial MIP solver substantially on larger problems. ALNS also found 24 new best solutions on a set of benchmark problems from the literature for the related Cooperative Orienteering Problem with Time Windows.

Citation: Christopher Garcia. The synchronized multi-assignment orienteering problem. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022018
References:
[1]

E. AngelelliC. Archetti and M. Vindigni, The clustered orienteering problem, European J. Oper. Res., 238 (2014), 404-414.  doi: 10.1016/j.ejor.2014.04.006.

[2]

C. ArchettiD. FeilletA. Hertz and M. G. Speranza, The capacitated team orienteering and profitable tour problems, Journal of the Operational Research Society, 60 (2009), 831-842.  doi: 10.1057/palgrave.jors.2602603.

[3]

Y. CaiZ. ZhangS. GuoH. Qin and A. Lim, A tree-based tabu search algorithm for the manpower allocation problem with time windows and job-teaming constraints, In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China, 3-9 (2013), 496-502. 

[4]

P. CappaneraL. Gouveia and M. G. Scutellà, The skill vehicle routing problem, Network Optimization, 6701 (2011), 354-364.  doi: 10.1007/978-3-642-21527-8_40.

[5]

A. M. CaunhyeX. Nie and S. Pokharel, Optimization models in emergency logistics: A literature review, Socio-economic Planning Sciences, 46 (2012), 4-13.  doi: 10.1016/j.seps.2011.04.004.

[6]

J. F. CordeauG. LaporteF. Pasin and S. Ropke, Scheduling technicians and tasks in a telecommunications company, J. Sched., 13 (2010), 393-409.  doi: 10.1007/s10951-010-0188-7.

[7]

I. M. ChaoB. L. Golden and E. A. Wasil, The team orienteering problem, European Journal of Operational Research, 88 (1996), 464-474.  doi: 10.1016/0377-2217(94)00289-4.

[8]

X. ChenB. W. Thomas and M. Hewitt, The technician routing problem with experience-based service times, Omega, 61 (2016), 49-61.  doi: 10.1016/j.omega.2015.07.006.

[9]

T. Cura, An artificial bee colony algorithm approach for the team orienteering problem with time windows, Computers & Industrial Engineering, 74 (2014), 270-290.  doi: 10.1016/j.cie.2014.06.004.

[10]

S. M. R. Davoodi and A. Goli, An integrated disaster relief model based on covering tour using hybrid Benders decomposition and variable neighborhood search: Application in the Iranian context, Computers & Industrial Engineering, 130 (2019), 370-380.  doi: 10.1016/j.cie.2019.02.040.

[11]

A. DohnE. Kolind and J. Clausen, The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Comput. Oper. Res., 36 (2009), 1145-1157.  doi: 10.1016/j.cor.2007.12.011.

[12]

P. F. Dutot, A. Laugier and A. M. Bustos, Technicians and Interventions Scheduling for Telecommunications, Technical report, France Telcom Research and Development, 2006.

[13]

L. EversA. I. BarrosH. Monsuur and A. Wgelmans, Online stochastic UAV mission planning with time windows and time-sensitive targets, European Journal of Operational Research, 238 (2014), 348-362.  doi: 10.1016/j.ejor.2014.03.014.

[14]

S. Faraj and Y. Xiao, Coordination in fast-response organizations, Management Science, 52 (2006), 1155-1169.  doi: 10.1287/mnsc.1060.0526.

[15]

L. M. GambardellaR. Montemanni and D. Weyland, Coupling ant colony systems with strong local searches, European J. Oper. Res., 220 (2012), 831-843.  doi: 10.1016/j.ejor.2012.02.038.

[16]

C. Garcia, Synchronized Multi-Assignment Orienteering, 1.1 (2021). doi: 10.5281/zenodo.5699598.

[17]

C. GarciaG. Rabadi and F. Handy, Dynamic resource allocation and coordination for high-load crisis volunteer management, Journal of Humanitarian Logistics and Supply Chain Management, 8 (2018), 533-556.  doi: 10.1108/JHLSCM-02-2018-0019.

[18]

D. GavalasV. KasapakisC. KonstantopoulosG. PantziouN. Vathis and C. Zaroliagis, The eCOMPASS multimodal tourist tour planner, Expert Systems with Applications, 42 (2015), 7303-7316.  doi: 10.1016/j.eswa.2015.05.046.

[19]

B. L. GoldenL. Levy and R. Vohra, The orienteering problem, Naval Research Logistics, 34 (1987), 307-318.  doi: 10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D.

[20]

A. GoliH. Khademi-ZareR. Tavakkoli-MoghaddamA. SadeghiehM. Sasanian and R. M. Kordestanizadeh, An integrated approach based on artificial intelligence and novel meta-heuristic algorithms to predict demand for dairy products: A case study, Network: Computation in Neural Systems, 32 (2021), 1-35.  doi: 10.1080/0954898X.2020.1849841.

[21]

A. Goli and B. Malmir, A covering tour approach for disaster relief locating and routing with fuzzy demand, International Journal of Intelligent Transportation Systems Research, 18 (2020), 140-152.  doi: 10.1007/s13177-019-00185-2.

[22]

A. GoliE. B. Tirkolaee and N. S. Aydin, Fuzzy integrated cell formation and production scheduling considering automated guided vehicles and human factors, IEEE Transactions on Fuzzy Systems, 29 (2021), 3686-3695.  doi: 10.1109/TFUZZ.2021.3053838.

[23]

A. GoliH. K. ZareR. Tavakkoli-Moghaddam and A. Sadeghieh, A comprehensive model of demand prediction based on hybrid artificial intelligence and metaheuristic algorithms: A case study in dairy industry, Journal of Industrial and Systems Engineering, 11 (2018), 190-203. 

[24]

A. GoliH. K. ZareR. Tavakkoli-Moghaddam and A. Sadeghieh, Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm, Numer. Algebra Control Optim., 9 (2019), 187-209.  doi: 10.3934/naco.2019014.

[25]

A. GunawanH. C. Lau and K. Lu, An iterated local search algorithm for solving the orienteering problem with time windows, Evolutionary Computation in Combinatorial Optimization, 9026 (2015), 61-73.  doi: 10.1007/978-3-319-16468-7_6.

[26]

A. Gunawan, H. C. Lau and K. Lu, SAILS: Hybrid algorithm for the team orienteering problem with time windows, Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015), Prague, Czech Republic (2015), 276–295.

[27]

A. Gunawan, H. C. Lau and K. Lu, Well-Tuned ILS for Extended Team Orienteering Problem with Time Windows, LARC Technical Report Series, Singapore Management University.

[28]

A. GunawanH. C. Lau and P. Vansteenwegen, Orienteering Problem: A survey of recent variants, solution approaches and applications, European J. Oper. Res, 255 (2016), 315-332.  doi: 10.1016/j.ejor.2016.04.059.

[29]

F. HammamiM. Rekik and L. C. Coelho, A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, Comput. Oper. Res., 123 (2020), 105034, 18 pp.  doi: 10.13140/RG.2.2.12346.54722.

[30]

H. HashimotoS. BoussierM. Vasquez and C. Wilbaut, A GRASP-based approach for technicians and interventions scheduling for telecommunications, Ann. Oper. Res., 183 (2011), 143-161.  doi: 10.1007/s10479-009-0545-0.

[31]

J. Holguín-VerasM. JallerL. N. Van WassenhoveN. Prez and T. Wachtendorf, Material convergence: Important and understudied disaster phenomenon, Natural Hazards Review, 15 (2012), 1-12. 

[32]

J. Holguín-VerasM. JallerL. N. Van WassenhoveN. Pérez and T. Wachtendorf, On the unique features of post-disaster humanitarian logistics, Journal of Operations Management, 30 (2012), 494-506. 

[33]

Q. Hu and A. Lim, An iterative three-component heuristic for the team orienteering problem with time windows, European Journal of Operational Research, 232 (2014), 276-286. 

[34]

C. A. Hurkens, Incorporating the strength of MIP modeling in schedule construction, RAIRO-Oper. Res., 43 (2009), 409-420.  doi: 10.1051/ro/2009026.

[35]

Y. Jiang and Y. Yuan, Emergency logistics in a large-scale disaster context: Achievements and challenges, Int. J. Environ. Res. Public Health, 16 (2019), 779 pp.  doi: 10.3390/ijerph16050779.

[36]

A. A. JuanA. FreixesJ. PanaderoC. Serrat and A. Estrada-Morena, Routing drones in smart cities: A biased-randomized algorithm, Transportation Research Procedia, 47 (2020), 243-250. 

[37]

M. G. Kantor and M. B. Rosenwein, The orienteering problem with time windows, Journal of the Operational Research Society, 43 (1992), 629-635. 

[38]

A. A. KovacsS. N. ParraghK. F. Doerner and R. F. Hartl, Adaptive large neighborhood search for service technician routing and scheduling problems, J. Sched., 15 (2012), 579-600.  doi: 10.1007/s10951-011-0246-9.

[39]

N. LabadieR. MansiniJ. Melechovsky and R. Wolfler Calvo, Hybridized evolutionary local search algorithm for the team orienteering problem with time windows, Journal of Heuristics, 17 (2011), 729-753. 

[40]

N. LabadieR. MansiniJ. Melechovsky and R. Wolfler Calvo, The team orienteering problem with time windows: An LP-based granular variable neighborhood search, European J. Oper. Res., 220 (2012), 15-27.  doi: 10.1016/j.ejor.2012.01.030.

[41]

K. LassiterA. Khademi and K. M. Taaffe, A robust optimization approach to volunteer management in humanitarian crises, International Journal of Production Economics, 163 (2015), 97-111.  doi: 10.1016/j.ijpe.2015.02.018.

[42]

Y. LiA. Lim and B. Rodrigues, Manpower Allocation with time windows and job teaming constraints, Naval Res. Logist., 52 (2005), 302-311.  doi: 10.1002/nav.20075.

[43]

S. W. Lin and V. F. Yu, A simulated annealing heuristic for the team orienteering problem with time windows, European J. Oper. Res., 217 (2012), 94-107.  doi: 10.1016/j.ejor.2011.08.024.

[44]

R. LiuY. Tao and X. Xie, An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits, Comput. Oper. Res., 101 (2019), 250-262.  doi: 10.1016/j.cor.2018.08.002.

[45]

M. Moskal and R. Batta, Adaptive unmanned aerial vehicle surveillance using a prize-collecting vertex routing model, Military Operations Research, 24 (2019), 5-22. 

[46]

E. H. ÖzderE. Özcan and T. Eran, A systematic literature review for personnel scheduling problems, International Journal of Information Technology & Decision Making, 19 (2020), 1695-1735. 

[47]

S. M. Pahlevan, S. M. S. Hosseini and A. Goli, Sustainable supply chain network design using products' life cycle in the aluminum industry, Environmental Science and Pollution Research, 2021. doi: 10.1007/s11356-020-12150-8.

[48]

V. Pillac, C. Gueret and A. Medaglia, On the dynamic technician routing and scheduling problem, ODYSSEUS 2012 - 5th International Workshop on Freight Transportation and Logistics, Mikonos, Greece (2012), 194.

[49]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.

[50]

I. RoozbehJ. W. Hearne and D. Pahlevani, A solution approach to the orienteering problem with time windows and synchronisation constraints, Heliyon, 6 (2020), e04202.  doi: 10.1016/j.heliyon.2020.e04202.

[51]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.  doi: 10.1287/trsc.1050.0135.

[52]

M. A. Salazar-AguilarA. Langevin and G. Laporte, The multi-district team orienteering problem, Comput. Oper. Res., 41 (2014), 76-82.  doi: 10.1016/j.cor.2013.07.026.

[53]

A. Santini, An adaptive large neighbourhood search algorithm for the orienteering problem, Expert Systems with Applications, 123 (2019), 154-167.  doi: 10.1016/j.eswa.2018.12.050.

[54]

B. Sarasola and K. Doerner, Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location, Networks, 75 (2020), 64-85.  doi: 10.1002/net.21905.

[55]

S. Schwarze and S. Voß, Improved load balancing and resource utilization for the skill vehicle routing problem, Optim. Lett., 7 (2013), 1805-1823.  doi: 10.1007/s11590-012-0524-2.

[56]

S. Schwarze and S. Voß, A bicriteria skill vehicle routing problem with time windows and an application to pushback operations at airports, Logistics Management, In: Dethloff J., Haasis HD., Kopfer H., Kotzab H., Schönberger J. (eds), (2014), 289–300. doi: 10.1007/978-3-319-13177-1_23.

[57]

W. SouffriauP. VansteenwegenG. Vanden Berghe and D. Van Oudheusden, The multiconstraint team orienteering problem with multiple time windows, Transportation Science, 47 (2013), 53-63. 

[58]

M. Van der Merwe, J. P. Minas, M. Ozlen and J. W. Hearne, The cooperative orienteering problem with time windows, Optimization Online, (2014).

[59]

P. Vansteenwegen and A. Gunawan, Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits, EURO Advanced Tutorials on Operational Research. Springer, Cham, 2019. doi: 10.1007/978-3-030-29746-6.

[60]

P. VansteenwegenW. Souffriau and D. Van Oudheusden, The orienteering problem: A survey, European J. Oper. Res., 209 (2011), 1-10.  doi: 10.1016/j.ejor.2010.03.045.

[61]

P. VansteenwegenW. SouffriauG. Vanden Berghe and D. Van Oudheusden, Iterated local search for the team orienteering problem with time windows, Computers & Operations Research, 36 (2009), 3281-3290. 

[62]

V. YuP. JewpanyaS. W. Lin and A. A. N. P. Redi, Team orienteering problem with time windows and time-dependent scores, Computers & Industrial Engineering, 127 (2019), 213-224.  doi: 10.1016/j.cie.2018.11.044.

[63]

B. YuanR. Liu and Z. Jiang, A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements, International Journal of Production Research, 53 (2015), 7450-7464.  doi: 10.1080/00207543.2015.1082041.

show all references

References:
[1]

E. AngelelliC. Archetti and M. Vindigni, The clustered orienteering problem, European J. Oper. Res., 238 (2014), 404-414.  doi: 10.1016/j.ejor.2014.04.006.

[2]

C. ArchettiD. FeilletA. Hertz and M. G. Speranza, The capacitated team orienteering and profitable tour problems, Journal of the Operational Research Society, 60 (2009), 831-842.  doi: 10.1057/palgrave.jors.2602603.

[3]

Y. CaiZ. ZhangS. GuoH. Qin and A. Lim, A tree-based tabu search algorithm for the manpower allocation problem with time windows and job-teaming constraints, In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China, 3-9 (2013), 496-502. 

[4]

P. CappaneraL. Gouveia and M. G. Scutellà, The skill vehicle routing problem, Network Optimization, 6701 (2011), 354-364.  doi: 10.1007/978-3-642-21527-8_40.

[5]

A. M. CaunhyeX. Nie and S. Pokharel, Optimization models in emergency logistics: A literature review, Socio-economic Planning Sciences, 46 (2012), 4-13.  doi: 10.1016/j.seps.2011.04.004.

[6]

J. F. CordeauG. LaporteF. Pasin and S. Ropke, Scheduling technicians and tasks in a telecommunications company, J. Sched., 13 (2010), 393-409.  doi: 10.1007/s10951-010-0188-7.

[7]

I. M. ChaoB. L. Golden and E. A. Wasil, The team orienteering problem, European Journal of Operational Research, 88 (1996), 464-474.  doi: 10.1016/0377-2217(94)00289-4.

[8]

X. ChenB. W. Thomas and M. Hewitt, The technician routing problem with experience-based service times, Omega, 61 (2016), 49-61.  doi: 10.1016/j.omega.2015.07.006.

[9]

T. Cura, An artificial bee colony algorithm approach for the team orienteering problem with time windows, Computers & Industrial Engineering, 74 (2014), 270-290.  doi: 10.1016/j.cie.2014.06.004.

[10]

S. M. R. Davoodi and A. Goli, An integrated disaster relief model based on covering tour using hybrid Benders decomposition and variable neighborhood search: Application in the Iranian context, Computers & Industrial Engineering, 130 (2019), 370-380.  doi: 10.1016/j.cie.2019.02.040.

[11]

A. DohnE. Kolind and J. Clausen, The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Comput. Oper. Res., 36 (2009), 1145-1157.  doi: 10.1016/j.cor.2007.12.011.

[12]

P. F. Dutot, A. Laugier and A. M. Bustos, Technicians and Interventions Scheduling for Telecommunications, Technical report, France Telcom Research and Development, 2006.

[13]

L. EversA. I. BarrosH. Monsuur and A. Wgelmans, Online stochastic UAV mission planning with time windows and time-sensitive targets, European Journal of Operational Research, 238 (2014), 348-362.  doi: 10.1016/j.ejor.2014.03.014.

[14]

S. Faraj and Y. Xiao, Coordination in fast-response organizations, Management Science, 52 (2006), 1155-1169.  doi: 10.1287/mnsc.1060.0526.

[15]

L. M. GambardellaR. Montemanni and D. Weyland, Coupling ant colony systems with strong local searches, European J. Oper. Res., 220 (2012), 831-843.  doi: 10.1016/j.ejor.2012.02.038.

[16]

C. Garcia, Synchronized Multi-Assignment Orienteering, 1.1 (2021). doi: 10.5281/zenodo.5699598.

[17]

C. GarciaG. Rabadi and F. Handy, Dynamic resource allocation and coordination for high-load crisis volunteer management, Journal of Humanitarian Logistics and Supply Chain Management, 8 (2018), 533-556.  doi: 10.1108/JHLSCM-02-2018-0019.

[18]

D. GavalasV. KasapakisC. KonstantopoulosG. PantziouN. Vathis and C. Zaroliagis, The eCOMPASS multimodal tourist tour planner, Expert Systems with Applications, 42 (2015), 7303-7316.  doi: 10.1016/j.eswa.2015.05.046.

[19]

B. L. GoldenL. Levy and R. Vohra, The orienteering problem, Naval Research Logistics, 34 (1987), 307-318.  doi: 10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D.

[20]

A. GoliH. Khademi-ZareR. Tavakkoli-MoghaddamA. SadeghiehM. Sasanian and R. M. Kordestanizadeh, An integrated approach based on artificial intelligence and novel meta-heuristic algorithms to predict demand for dairy products: A case study, Network: Computation in Neural Systems, 32 (2021), 1-35.  doi: 10.1080/0954898X.2020.1849841.

[21]

A. Goli and B. Malmir, A covering tour approach for disaster relief locating and routing with fuzzy demand, International Journal of Intelligent Transportation Systems Research, 18 (2020), 140-152.  doi: 10.1007/s13177-019-00185-2.

[22]

A. GoliE. B. Tirkolaee and N. S. Aydin, Fuzzy integrated cell formation and production scheduling considering automated guided vehicles and human factors, IEEE Transactions on Fuzzy Systems, 29 (2021), 3686-3695.  doi: 10.1109/TFUZZ.2021.3053838.

[23]

A. GoliH. K. ZareR. Tavakkoli-Moghaddam and A. Sadeghieh, A comprehensive model of demand prediction based on hybrid artificial intelligence and metaheuristic algorithms: A case study in dairy industry, Journal of Industrial and Systems Engineering, 11 (2018), 190-203. 

[24]

A. GoliH. K. ZareR. Tavakkoli-Moghaddam and A. Sadeghieh, Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm, Numer. Algebra Control Optim., 9 (2019), 187-209.  doi: 10.3934/naco.2019014.

[25]

A. GunawanH. C. Lau and K. Lu, An iterated local search algorithm for solving the orienteering problem with time windows, Evolutionary Computation in Combinatorial Optimization, 9026 (2015), 61-73.  doi: 10.1007/978-3-319-16468-7_6.

[26]

A. Gunawan, H. C. Lau and K. Lu, SAILS: Hybrid algorithm for the team orienteering problem with time windows, Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015), Prague, Czech Republic (2015), 276–295.

[27]

A. Gunawan, H. C. Lau and K. Lu, Well-Tuned ILS for Extended Team Orienteering Problem with Time Windows, LARC Technical Report Series, Singapore Management University.

[28]

A. GunawanH. C. Lau and P. Vansteenwegen, Orienteering Problem: A survey of recent variants, solution approaches and applications, European J. Oper. Res, 255 (2016), 315-332.  doi: 10.1016/j.ejor.2016.04.059.

[29]

F. HammamiM. Rekik and L. C. Coelho, A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, Comput. Oper. Res., 123 (2020), 105034, 18 pp.  doi: 10.13140/RG.2.2.12346.54722.

[30]

H. HashimotoS. BoussierM. Vasquez and C. Wilbaut, A GRASP-based approach for technicians and interventions scheduling for telecommunications, Ann. Oper. Res., 183 (2011), 143-161.  doi: 10.1007/s10479-009-0545-0.

[31]

J. Holguín-VerasM. JallerL. N. Van WassenhoveN. Prez and T. Wachtendorf, Material convergence: Important and understudied disaster phenomenon, Natural Hazards Review, 15 (2012), 1-12. 

[32]

J. Holguín-VerasM. JallerL. N. Van WassenhoveN. Pérez and T. Wachtendorf, On the unique features of post-disaster humanitarian logistics, Journal of Operations Management, 30 (2012), 494-506. 

[33]

Q. Hu and A. Lim, An iterative three-component heuristic for the team orienteering problem with time windows, European Journal of Operational Research, 232 (2014), 276-286. 

[34]

C. A. Hurkens, Incorporating the strength of MIP modeling in schedule construction, RAIRO-Oper. Res., 43 (2009), 409-420.  doi: 10.1051/ro/2009026.

[35]

Y. Jiang and Y. Yuan, Emergency logistics in a large-scale disaster context: Achievements and challenges, Int. J. Environ. Res. Public Health, 16 (2019), 779 pp.  doi: 10.3390/ijerph16050779.

[36]

A. A. JuanA. FreixesJ. PanaderoC. Serrat and A. Estrada-Morena, Routing drones in smart cities: A biased-randomized algorithm, Transportation Research Procedia, 47 (2020), 243-250. 

[37]

M. G. Kantor and M. B. Rosenwein, The orienteering problem with time windows, Journal of the Operational Research Society, 43 (1992), 629-635. 

[38]

A. A. KovacsS. N. ParraghK. F. Doerner and R. F. Hartl, Adaptive large neighborhood search for service technician routing and scheduling problems, J. Sched., 15 (2012), 579-600.  doi: 10.1007/s10951-011-0246-9.

[39]

N. LabadieR. MansiniJ. Melechovsky and R. Wolfler Calvo, Hybridized evolutionary local search algorithm for the team orienteering problem with time windows, Journal of Heuristics, 17 (2011), 729-753. 

[40]

N. LabadieR. MansiniJ. Melechovsky and R. Wolfler Calvo, The team orienteering problem with time windows: An LP-based granular variable neighborhood search, European J. Oper. Res., 220 (2012), 15-27.  doi: 10.1016/j.ejor.2012.01.030.

[41]

K. LassiterA. Khademi and K. M. Taaffe, A robust optimization approach to volunteer management in humanitarian crises, International Journal of Production Economics, 163 (2015), 97-111.  doi: 10.1016/j.ijpe.2015.02.018.

[42]

Y. LiA. Lim and B. Rodrigues, Manpower Allocation with time windows and job teaming constraints, Naval Res. Logist., 52 (2005), 302-311.  doi: 10.1002/nav.20075.

[43]

S. W. Lin and V. F. Yu, A simulated annealing heuristic for the team orienteering problem with time windows, European J. Oper. Res., 217 (2012), 94-107.  doi: 10.1016/j.ejor.2011.08.024.

[44]

R. LiuY. Tao and X. Xie, An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits, Comput. Oper. Res., 101 (2019), 250-262.  doi: 10.1016/j.cor.2018.08.002.

[45]

M. Moskal and R. Batta, Adaptive unmanned aerial vehicle surveillance using a prize-collecting vertex routing model, Military Operations Research, 24 (2019), 5-22. 

[46]

E. H. ÖzderE. Özcan and T. Eran, A systematic literature review for personnel scheduling problems, International Journal of Information Technology & Decision Making, 19 (2020), 1695-1735. 

[47]

S. M. Pahlevan, S. M. S. Hosseini and A. Goli, Sustainable supply chain network design using products' life cycle in the aluminum industry, Environmental Science and Pollution Research, 2021. doi: 10.1007/s11356-020-12150-8.

[48]

V. Pillac, C. Gueret and A. Medaglia, On the dynamic technician routing and scheduling problem, ODYSSEUS 2012 - 5th International Workshop on Freight Transportation and Logistics, Mikonos, Greece (2012), 194.

[49]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.

[50]

I. RoozbehJ. W. Hearne and D. Pahlevani, A solution approach to the orienteering problem with time windows and synchronisation constraints, Heliyon, 6 (2020), e04202.  doi: 10.1016/j.heliyon.2020.e04202.

[51]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.  doi: 10.1287/trsc.1050.0135.

[52]

M. A. Salazar-AguilarA. Langevin and G. Laporte, The multi-district team orienteering problem, Comput. Oper. Res., 41 (2014), 76-82.  doi: 10.1016/j.cor.2013.07.026.

[53]

A. Santini, An adaptive large neighbourhood search algorithm for the orienteering problem, Expert Systems with Applications, 123 (2019), 154-167.  doi: 10.1016/j.eswa.2018.12.050.

[54]

B. Sarasola and K. Doerner, Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location, Networks, 75 (2020), 64-85.  doi: 10.1002/net.21905.

[55]

S. Schwarze and S. Voß, Improved load balancing and resource utilization for the skill vehicle routing problem, Optim. Lett., 7 (2013), 1805-1823.  doi: 10.1007/s11590-012-0524-2.

[56]

S. Schwarze and S. Voß, A bicriteria skill vehicle routing problem with time windows and an application to pushback operations at airports, Logistics Management, In: Dethloff J., Haasis HD., Kopfer H., Kotzab H., Schönberger J. (eds), (2014), 289–300. doi: 10.1007/978-3-319-13177-1_23.

[57]

W. SouffriauP. VansteenwegenG. Vanden Berghe and D. Van Oudheusden, The multiconstraint team orienteering problem with multiple time windows, Transportation Science, 47 (2013), 53-63. 

[58]

M. Van der Merwe, J. P. Minas, M. Ozlen and J. W. Hearne, The cooperative orienteering problem with time windows, Optimization Online, (2014).

[59]

P. Vansteenwegen and A. Gunawan, Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits, EURO Advanced Tutorials on Operational Research. Springer, Cham, 2019. doi: 10.1007/978-3-030-29746-6.

[60]

P. VansteenwegenW. Souffriau and D. Van Oudheusden, The orienteering problem: A survey, European J. Oper. Res., 209 (2011), 1-10.  doi: 10.1016/j.ejor.2010.03.045.

[61]

P. VansteenwegenW. SouffriauG. Vanden Berghe and D. Van Oudheusden, Iterated local search for the team orienteering problem with time windows, Computers & Operations Research, 36 (2009), 3281-3290. 

[62]

V. YuP. JewpanyaS. W. Lin and A. A. N. P. Redi, Team orienteering problem with time windows and time-dependent scores, Computers & Industrial Engineering, 127 (2019), 213-224.  doi: 10.1016/j.cie.2018.11.044.

[63]

B. YuanR. Liu and Z. Jiang, A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements, International Journal of Production Research, 53 (2015), 7450-7464.  doi: 10.1080/00207543.2015.1082041.

Figure 1.  Node insertion process. The black node is to be inserted, and the arcs represent different agent routes. The dotted and dashed agents can fill the roles needed by the new node, so the current assignment and arc lists are updated to incorporate this routing modification
Figure 2.  Average percent of best solution found by problem set
Figure 3.  Average solution time by problem set
Table 1.  Problem generation parameter descriptions. All time units are in minutes
Parameter Description
Num. Workers Number of workers/agents
Num. Jobs Number of jobs
Num. Roles Number of distinct roles
Ptime Size Range The range that job processing times may take
Max Time The maximum time in any problem
Role Frequencies A list of numbers in (0, 1) corresponding to each role. Represents the proportion of agents qualified for the roles.
Job Demand Range The minimum and maximum total count of agents required at a job
Num. Templates A job template specifies the number of workers required in each role. Each job will use exactly one template, and this parameter specifies the number of unique job templates to generate.
Reward Range The range that job rewards may take
Num. Multi-option Jobs The number of mutually exclusive job pairs
Depot The number of agents that will be depot-based (versus ad-hoc)
Max Travel Time The maximum travel time between any two nodes
Job Step Size The job time window increment size. Job time windows are generated as multiples of this (e.g., increments of 30 minutes)
Worker Step Size The ad-hoc worker availability time window increment size (analogous to Job Step Size)
Job Min Open/Job Max Close The earliest open time/latest close time of any job time window
Worker Min Open/Worker Max Close The earliest open time/latest close time of any worker availability
Parameter Description
Num. Workers Number of workers/agents
Num. Jobs Number of jobs
Num. Roles Number of distinct roles
Ptime Size Range The range that job processing times may take
Max Time The maximum time in any problem
Role Frequencies A list of numbers in (0, 1) corresponding to each role. Represents the proportion of agents qualified for the roles.
Job Demand Range The minimum and maximum total count of agents required at a job
Num. Templates A job template specifies the number of workers required in each role. Each job will use exactly one template, and this parameter specifies the number of unique job templates to generate.
Reward Range The range that job rewards may take
Num. Multi-option Jobs The number of mutually exclusive job pairs
Depot The number of agents that will be depot-based (versus ad-hoc)
Max Travel Time The maximum travel time between any two nodes
Job Step Size The job time window increment size. Job time windows are generated as multiples of this (e.g., increments of 30 minutes)
Worker Step Size The ad-hoc worker availability time window increment size (analogous to Job Step Size)
Job Min Open/Job Max Close The earliest open time/latest close time of any job time window
Worker Min Open/Worker Max Close The earliest open time/latest close time of any worker availability
Table 2.  Problem generation parameter settings corresponding to the different design factor levels
Parameter Name Baseline Value (-) D(0) D(+) S(0) S(+) T(+)
Num. Workers 15 30 75
Num. Jobs 10 20 50
Num. Roles 3 5
Depot Num. Workers Num. Workers/2 0
Job Demand Range [1, 3] [3, 5]
Num. Templates 5 15
Num. Multi-option Jobs 0.3×Num. Jobs 0
Role Frequencies [0.4, 0.8, 0.4] [0.3, 0.3, 0.2, 0.2, 0.2]
Max. Travel Time 30 60
Parameter Name Baseline Value (-) D(0) D(+) S(0) S(+) T(+)
Num. Workers 15 30 75
Num. Jobs 10 20 50
Num. Roles 3 5
Depot Num. Workers Num. Workers/2 0
Job Demand Range [1, 3] [3, 5]
Num. Templates 5 15
Num. Multi-option Jobs 0.3×Num. Jobs 0
Role Frequencies [0.4, 0.8, 0.4] [0.3, 0.3, 0.2, 0.2, 0.2]
Max. Travel Time 30 60
Table 3.  Comparison of solution quality (main experiment)
Design Factor No. Optimal Found(out of 10) No. Best Solutions (out of 10) Avg. Percent Best Solution Found
Problem Set D S T CPLEX ALNS CPLEX ALNS CPLEX ALNS
1 - - - 10 10 10 10 100 100
2 - - + 9 5 10 6 100 99
3 - 0 - 10 10 10 10 100 100
4 - 0 + 9 9 9 10 99 100
5 - + - 7 7 7 10 81 100
6 - + + 0 0 0 10 2 100
7 0 - - 10 10 10 10 100 100
8 0 - + 9 5 10 5 100 97
9 0 0 - 10 10 10 10 100 100
10 0 0 + 1 1 1 10 80 100
11 0 + - 2 2 2 10 39 100
12 0 + + 0 0 0 10 3 100
13 + - - 10 10 10 10 100 100
14 + - + 10 5 10 5 100 96
15 + 0 - 9 9 10 10 100 100
16 + 0 + 0 0 2 9 75 100
17 + + - 1 1 1 10 42 100
18 + + + 0 0 0 10 2 100
Design Factor No. Optimal Found(out of 10) No. Best Solutions (out of 10) Avg. Percent Best Solution Found
Problem Set D S T CPLEX ALNS CPLEX ALNS CPLEX ALNS
1 - - - 10 10 10 10 100 100
2 - - + 9 5 10 6 100 99
3 - 0 - 10 10 10 10 100 100
4 - 0 + 9 9 9 10 99 100
5 - + - 7 7 7 10 81 100
6 - + + 0 0 0 10 2 100
7 0 - - 10 10 10 10 100 100
8 0 - + 9 5 10 5 100 97
9 0 0 - 10 10 10 10 100 100
10 0 0 + 1 1 1 10 80 100
11 0 + - 2 2 2 10 39 100
12 0 + + 0 0 0 10 3 100
13 + - - 10 10 10 10 100 100
14 + - + 10 5 10 5 100 96
15 + 0 - 9 9 10 10 100 100
16 + 0 + 0 0 2 9 75 100
17 + + - 1 1 1 10 42 100
18 + + + 0 0 0 10 2 100
Table 4.  Solution times, CPLEX solutions found, and ALNS variability (main experiment)
Design Factor Avg. Solution Time (sec.) No. CPLEX Feasible Solutions ALNS Min/Max
Problem Set D S T CPLEX ALNS Found (out of 10) Variability Percent
1 - - - 0 2 10 100
2 - - + 256 8 10 98
3 - 0 - 2 5 10 100
4 - 0 + 343 18 10 100
5 - + - 703 21 10 100
6 - + + 1201 47 6 100
7 0 - - 1 2 10 100
8 0 - + 161 14 10 96
9 0 0 - 57 4 10 100
10 0 0 + 1109 31 10 97
11 0 + - 1094 17 10 100
12 0 + + 1201 107 7 99
13 + - - 0 1 10 100
14 + - + 51 13 10 96
15 + 0 - 204 4 10 100
16 + 0 + 1200 30 10 94
17 + + - 1106 14 10 100
18 + + + 1201 141 7 98
Design Factor Avg. Solution Time (sec.) No. CPLEX Feasible Solutions ALNS Min/Max
Problem Set D S T CPLEX ALNS Found (out of 10) Variability Percent
1 - - - 0 2 10 100
2 - - + 256 8 10 98
3 - 0 - 2 5 10 100
4 - 0 + 343 18 10 100
5 - + - 703 21 10 100
6 - + + 1201 47 6 100
7 0 - - 1 2 10 100
8 0 - + 161 14 10 96
9 0 0 - 57 4 10 100
10 0 0 + 1109 31 10 97
11 0 + - 1094 17 10 100
12 0 + + 1201 107 7 99
13 + - - 0 1 10 100
14 + - + 51 13 10 96
15 + 0 - 204 4 10 100
16 + 0 + 1200 30 10 94
17 + + - 1106 14 10 100
18 + + + 1201 141 7 98
Table 5.  Results on large benchmark problems used in Roozbeh et al. (2020)
Average
Problem Class No. Team Members Percent Best Percent Avg. No. New Best Solutions Found Avg. Time (sec.)
C100 4 98 96 1 118
C100 6 96 95 0 151
C200 4 96 96 0 317
C200 6 97 97 0 296
R100 4 95 91 1 33
R100 6 93 91 1 41
R200 4 100 101 7 214
R200 6 101 102 9 191
RC100 4 92 89 0 32
RC100 6 94 90 0 40
RC200 4 97 96 2 192
RC200 6 98 98 3 177
Overall 96 95 24 142
Average
Problem Class No. Team Members Percent Best Percent Avg. No. New Best Solutions Found Avg. Time (sec.)
C100 4 98 96 1 118
C100 6 96 95 0 151
C200 4 96 96 0 317
C200 6 97 97 0 296
R100 4 95 91 1 33
R100 6 93 91 1 41
R200 4 100 101 7 214
R200 6 101 102 9 191
RC100 4 92 89 0 32
RC100 6 94 90 0 40
RC200 4 97 96 2 192
RC200 6 98 98 3 177
Overall 96 95 24 142
Table 6.  New best solutions found from benchmark instances in Roozbeh et al. (2020)
Problem Instance No. Vehicles Best Previously Reported Objective Function New Best Found Improvement %
c101 4 580 590 1.72
r111 6 644 648 0.62
r112 4 517 524 1.35
r202 6 1302 1308 0.46
r203 6 1349 1362 0.96
r204 4 1194 1202 0.67
r204 6 1362 1391 2.13
r206 4 1135 1152 1.5
r206 6 1304 1331 2.07
r207 4 1143 1167 2.1
r207 6 1340 1365 1.87
r208 4 1147 1193 4.01
r208 6 1357 1399 3.1
r209 4 1129 1130 0.09
r209 6 1279 1308 2.27
r210 4 1098 1150 4.74
r210 6 1313 1320 0.53
r211 4 1133 1173 3.53
r211 6 1310 1352 3.21
rc203 6 1513 1518 0.33
rc206 6 1435 1449 0.98
rc207 4 1172 1221 4.18
rc207 6 1456 1475 1.3
rc208 4 1248 1297 3.93
Problem Instance No. Vehicles Best Previously Reported Objective Function New Best Found Improvement %
c101 4 580 590 1.72
r111 6 644 648 0.62
r112 4 517 524 1.35
r202 6 1302 1308 0.46
r203 6 1349 1362 0.96
r204 4 1194 1202 0.67
r204 6 1362 1391 2.13
r206 4 1135 1152 1.5
r206 6 1304 1331 2.07
r207 4 1143 1167 2.1
r207 6 1340 1365 1.87
r208 4 1147 1193 4.01
r208 6 1357 1399 3.1
r209 4 1129 1130 0.09
r209 6 1279 1308 2.27
r210 4 1098 1150 4.74
r210 6 1313 1320 0.53
r211 4 1133 1173 3.53
r211 6 1310 1352 3.21
rc203 6 1513 1518 0.33
rc206 6 1435 1449 0.98
rc207 4 1172 1221 4.18
rc207 6 1456 1475 1.3
rc208 4 1248 1297 3.93
[1]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021197

[2]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021225

[3]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045

[4]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[5]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[6]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[7]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[8]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240

[9]

Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701

[10]

Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119

[11]

Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026

[12]

Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2073-2095. doi: 10.3934/jimo.2020059

[13]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200

[14]

Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012

[15]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[16]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1651-1663. doi: 10.3934/jimo.2021037

[17]

Min Zhang, Guowen Xiong, Shanshan Bao, Chao Meng. A time-division distribution strategy for the two-echelon vehicle routing problem with demand blowout. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2847-2872. doi: 10.3934/jimo.2021094

[18]

Rocio de la Torre, Amaia Lusa, Manuel Mateo, El-Houssaine Aghezzaf. Determining personnel promotion policies in HEI. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1835-1859. doi: 10.3934/jimo.2019031

[19]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[20]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (292)
  • HTML views (188)
  • Cited by (0)

Other articles
by authors

[Back to Top]