\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

The synchronized multi-assignment orienteering problem

Abstract / Introduction Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90B06, 90B70.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [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.
  • 加载中

Figures(3)

Tables(6)

SHARE

Article Metrics

HTML views(2221) PDF downloads(491) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return