The synchronized multi-assignment orienteering problem

Christopher Garcia

doi:10.3934/jimo.2022018

Article Contents

2023, Volume 19, Issue 3: 1790-1812. Doi: 10.3934/jimo.2022018

This issue Previous Article Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem Next Article An inertial triple-projection algorithm for solving the split feasibility problem

The synchronized multi-assignment orienteering problem

Christopher Garcia

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

Received: June 2021

Revised: November 2021

Early access: February 2022

Published: March 2023

Abstract Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

Figure 2. Average percent of best solution found by problem set

Download: Full-size image PowerPoint slide

Figure 3. Average solution time by problem set

Download: Full-size image PowerPoint slide

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

Related Papers

Cited by

References

[1]	E. Angelelli, C. 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. Archetti, D. Feillet, A. 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. Cai, Z. Zhang, S. Guo, H. 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. Cappanera, L. 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. Caunhye, X. 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. Cordeau, G. Laporte, F. 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. Chao, B. 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. Chen, B. 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. Dohn, E. 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. Evers, A. I. Barros, H. 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. Gambardella, R. 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. Garcia, G. 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. Gavalas, V. Kasapakis, C. Konstantopoulos, G. Pantziou, N. 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. Golden, L. 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. Goli, H. Khademi-Zare, R. Tavakkoli-Moghaddam, A. Sadeghieh, M. 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. Goli, E. 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. Goli, H. K. Zare, R. 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. Goli, H. K. Zare, R. 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. Gunawan, H. 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. Gunawan, H. 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. Hammami, M. 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. Hashimoto, S. Boussier, M. 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-Veras, M. Jaller, L. N. Van Wassenhove, N. Prez and T. Wachtendorf, Material convergence: Important and understudied disaster phenomenon, Natural Hazards Review, 15 (2012), 1-12.
[32]	J. Holguín-Veras, M. Jaller, L. N. Van Wassenhove, N. 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. Juan, A. Freixes, J. Panadero, C. 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. Kovacs, S. N. Parragh, K. 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. Labadie, R. Mansini, J. 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. Labadie, R. Mansini, J. 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. Lassiter, A. 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. Li, A. 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. Liu, Y. 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. Özder, E. Ö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. Roozbeh, J. 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-Aguilar, A. 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. Souffriau, P. Vansteenwegen, G. 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. Vansteenwegen, W. 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. Vansteenwegen, W. Souffriau, G. 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. Yu, P. Jewpanya, S. 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. Yuan, R. 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.