A multi-start route improving matheuristic for the production routeing problem

Figures & data

Figure 1. Illustration of calculating the costs of removing node b from route r and inserting node e at position 5 in route r. Route r is marked with solid lines and the insertion and removal with dotted lines.

A route consisting of the depot and nodes a, b, c and d. The node e is not in the route. We then have the following: i r(1)=a, i r(3)=c, i r(4)=d, i r(5)=0, p r(b)=2 and p * r(e)=5.

Figure 2. A route consisting of the depot and nodes a, b, c and d is changed to a route consisting of the depot and nodes b, d and e. The cost of the route is then changed from $C_{0a}+C_{\mathrm{ab}}+C_{\mathrm{bc}}+C_{\mathrm{cd}}+C_{d0}$ to $C_{0b}+C_{\mathrm{bd}}+C_{\mathrm{de}}+C_{e0}$.

An example showing the cost calculations when b, d and e are included in route r and a and c are excluded. The route cost C R r is calculated based on the original route, and the cost of choosing route r and including b, d and e is shown to be correct.

Table 1. An overview of all solution methods for the PRP.

Reference	Abbreviation	Sol	CPU	#Threads	Solver
Schenekemberg et al. (2021)	SSPG-BC	E	Intel(R) Xeon(R) 2.60 GHz	6	Gurobi 8.1
Adulyasak, Cordeau, and Jans (2014a)	ACJ-BC	E	AMD Opteron 2.40 GHz	8	CPLEX 12.3
Boudia and Prins (2009)	BP-MA	H	2.30 GHz PC	1	–
Adulyasak, Cordeau, and Jans (2014b)	ACJ-ALNS-500	H	2.10 GHz Duo CPU PC	Def	CPLEX 12.2
	ACJ-ALNS-1000	H
Qiu et al. (2018)	QWXFP-VNS	H	Intel Core 2 Duo P8600 2.40 GHz	Def	CPLEX 12.6
Absi et al. (2015)	AADF-VRP	M	Xeon 2.67 GHz PC	Def	CPLEX 12.1
	AADF-MTSP	M
Solyalı and Süral (2017)	SS-M	M	2.40 GHz PC	12	CPLEX 12.5
Chitsaz, Cordeau, and Jans (2019)	CCJ-M	M	Xeon X5650 2.67 GHz	1	CPLEX 12.6
Li et al. (2019)	LCCF-M	M	Intel Core i7 2.5 GHz	Def	CPLEX 12.6
Avci and Yildiz (2019)	AY-M	M	Intel Core i5-760X 4.00 GHz	Def	CPLEX 12.6
Manousakis et al. (2022)	MKKZ-M	M	Intel Core i7-7700 3.60 GHz	1	Gurobi 9.0.2
This paper	VACS-M	M	Xeon Gold 6144 3.5 GHz	1	Gurobi 9.1

Note: Def = Default, Sol = Solution method, E = Exact method, H = Heuristic, M = Matheuristic.

Table 2. The number of instances solved by each solution method.

			SSPG-BC	ACJ-BC	BP-MA	ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	AY-M	MKKZ-M	VACS-M
Set	V	Size	E	E	H	H	H	H	M	M	M	M	M	M	M	M
A2-1	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A2-2	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A2-3	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A2-4	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A3-1	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A3-2	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A3-3	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
A3-4	∞	120	–	–	–	120	120	120	120	120	120	120	120	120	120	120
B1	5	30	30	–	30	30	30	30	30	30	30	30	30	–	30	30
B2	9	30	30	–	30	30	30	30	30	30	30	30	30	–	30	30
B3	13	30	–	–	30	30	–	30	30	30	30	30	30	–	30	30
C	2–4	168	168	168	–	168	–	–	–	–	–	–	–	–	–	168

Note: V = Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic.

Table 3. Parameter values.

Name	Value
α	1/V
β	0.975
γ	0.25
δ	4
ω	3 ($-3\mathrm{\%},+3\mathrm{\%},+6\mathrm{\%}$)
${ϵ}_1$	1
${ϵ}_2$	3
${ϵ}_3$	3
it	5
Time Limit: Initial solution	$0.5\left|N\right|$
Time Limit: Improvement model 1	$\left|N\right|$
Time Limit: Improvement model 2	$10\left|T^{\prime }\right|+0.5\left|N\right|$

Table 4. The average results for the Adulyasak instances.

		ACJ-BC			ACJ-ALNS			SSPG-BC			VACS-M
Set	Size	Gap	Time	#BKS	Gap	Time	#BKS	Gap	Time	#BKS	Gap	Time	#BKS	New
C-10	24	0.00	64	24 (24)	1.03	–	2 (2)	0.00	13	24 (24)	0.32	5	9 (9)	0
C-15	24	0.01	7734	20 (20)	1.41	–	2 (2)	0.00	2540	24 (20)	0.59	12	4 (4)	0
C-20	24	0.01	4084	23 (22)	1.37	–	2 (2)	0.00	1030	24 (24)	0.20	8	9 (9)	0
C-25	24	0.06	10,535	20 (20)	1.39	–	1 (1)	0.00	1984	23 (22)	0.29	18	6 (6)	0
C-30	24	0.37	20,621	14 (14)	1.61	–	0 (0)	0.00	5787	24 (16)	0.57	73	2 (2)	0
C-35	16	0.16	20,563	11 (11)	1.97	–	0 (0)	0.00	4800	16 (13)	0.39	18	2 (2)	0
C-40	16	0.27	29,370	7 (7)	1.05	–	0 (0)	0.00	9860	12 (7)	0.16	17	5 (1)	3
C-45	8	0.34	27,798	5 (5)	1.15	–	1 (1)	0.03	12,652	4 (2)	0.59	12	2 (1)	1
C-50	8	0.04	21,318	5 ( 5)	1.60	–	0 (0)	0.00	6404	7 (6)	0.53	11	2 (1)	1
Sum/Avg.		0.12	13,243	129 (128)	1.39	–	8 (8)	0.00	3926	158 (134)	0.39	21	41 (35)	5

Note: #BKS = Number of best-known solutions.

Table 5. The average gaps in percentage for the Archetti instances.

			ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	AY-M	MKKZ-M	VACS-M
Set	V	Size	H	H	H	M	M	M	M	M	M	M	M
A2-1	∞	120	1.36	1.35	0.26	0.38	1.30	0.27	0.16	0.21	0.18	0.02	0.04
A2-2	∞	120	0.22	0.22	0.08	0.10	0.14	0.06	0.06	0.05	0.06	0.00	0.02
A2-3	∞	120	4.63	4.39	0.87	1.83	3.57	0.92	0.62	0.82	0.78	0.06	0.15
A2-4	∞	120	0.36	0.35	0.13	0.25	0.62	0.21	0.13	0.18	0.17	0.06	$\mathbf{\text{-0.01}}$
A3-1	∞	120	1.10	1.05	0.23	0.27	1.91	0.12	0.23	0.08	0.07	0.19	$\mathbf{\text{-0.05}}$
A3-2	∞	120	0.17	0.16	0.08	0.06	0.14	0.04	0.04	0.03	0.05	0.00	0.00
A3-3	∞	120	4.16	3.97	0.62	1.54	4.13	0.46	1.38	0.47	0.55	0.37	$\mathbf{\text{-0.18}}$
A3-4	∞	120	0.37	0.35	0.10	0.26	0.72	0.07	0.08	0.06	0.11	0.14	$\mathbf{\text{-0.08}}$
Average			1.54	1.48	0.30	0.59	1.57	0.27	0.34	0.24	0.24	0.11	$\mathbf{\text{-0.01}}$

Note: $V=$ Number of vehicles, H = Heuristic, M = Matheuristic.

Table 6. The number of best-known solutions (BKSs) for the Archetti instances.

			ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	AY-M	MKKZ-M	VACS-M
Set	V	Size	H	H	H	M	M	M	M	M	M	M	M
A2-1	∞	120	0	0	0	0	0	2	22	2	9	57	62 (41)
A2-2	∞	120	0	0	0	0	0	0	1	2	0	99	18 (18)
A2-3	∞	120	0	0	0	0	0	2	7	0	3	61	58 (52)
A2-4	∞	120	0	0	2	0	1	0	4	0	4	69	44 (41)
A3-1	∞	120	0	0	0	0	0	2	4	1	5	6	102 (102)
A3-2	∞	120	0	0	0	3	0	0	3	2	0	57	55 (55)
A3-3	∞	120	0	0	0	0	0	2	0	2	2	19	95 (95)
A3-4	∞	120	0	0	0	1	0	0	6	3	0	29	82 (81)
Total			0	0	2	4	1	8	47	12	23	397	516 (485)

Note: The number within parentheses refers to the number of strictly improving solutions. $V=$ Number of vehicles, H = Heuristic, M = Matheuristic.

Table 7. The average computing time in seconds for the Archetti instances.

			ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	AY-M	MKKZ-M*	VACS-M
Set	V	Size	H	H	H	M	M	M	M	M	M	M	M
A2-1	∞	120	29	50	25	23	315	16	400	43	89	1513	130
A2-2	∞	120	28	50	21	23	288	14	344	37	78	1563	103
A2-3	∞	120	24	43	25	26	335	16	309	39	78	1832	156
A2-4	∞	120	26	44	28	26	330	25	434	42	84	1409	142
A3-1	∞	120	136	249	85	86	514	324	2125	169	187	10,174	857
A3-2	∞	120	125	221	73	76	497	51	1947	132	102	11,073	508
A3-3	∞	120	107	191	73	75	509	350	1461	145	290	11,013	978
A3-4	∞	120	108	189	84	87	507	125	2213	160	176	11,760	605
Average			73	130	52	53	412	115	1154	95	135	6292	435

Note: $V=$ Number of vehicles, H = Heuristic, M = Matheuristic, * = estimated time

Table 8. The average gap in percentage for the Boudia instances.

			SSPG-BC	BP-MA	ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	MKKZ-M	VACS-M
Set	V	Size	E	H	H	H	H	M	M	M	M	M	M	M
B1	5	30	3.23	15.73	2.19	2.08	1.75	2.70	2.46	1.06	1.81	1.32	0.00	0.02
B2	9	30	12.46	13.99	1.62	1.60	1.26	1.50	1.97	0.71	1.86	0.55	0.07	−0.54
B3	13	30	–	17.33	2.70	–	1.27	1.43	3.02	3.34	1.25	0.41	0.20	−0.94
Average			7.84	15.68	2.17	1.84	1.42	1.87	2.48	1.70	1.64	0.76	0.09	−0.49

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, – = The instances are not solved by the solution method.

Table 9. The number of best-known solutions (BKSs) for the Boudia instances.

			SSPG-BC	BP-MA	ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	MKKZ-M	VACS-M
Set	V	Size	E	H	H	H	H	M	M	M	M	M	M	M
B1	5	30	0	0	0	0	0	0	0	0	0	0	15	15 (15)
B2	9	30	0	0	0	0	0	0	0	0	0	0	0	30 (30)
B3	13	30	–	0	0	–	0	0	0	0	0	0	0	30 (30)
Total			0	0	0	0	0	0	0	0	0	0	15	75 (75)

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, – = The instances are not solved by the solution method.

Table 10. The average computing time in seconds for the Boudia instances.

			ASSPG-BC	BP-MA	ACJ-ALNS-500	ACJ-ALNS-1000	QWXFP-VNS	AADF-VRP	AADF-MTSP	SS-M	CCJ-M	LCCF-M	MKKZ-M*	VACS-M
Set	V	Size	E	H	H	H	H	M	M	M	M	M	M	M
B1	5	30	14,400	117	298	481	488	298	481	2464	3559	277	31,750	1543
B2	9	30	14,400	976	1405	1570	1767	1405	1570	7487	9811	493	82,194	4784
B3	13	30	–	1148	5794	–	5884	4197	19,270	16,365	15,891	614	202,111	8712
Average			14,400	747	2499	1025	2713	1977	7107	8772	9754	461	105,351	5013

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, *= estimated time, – = The instances are not solved by the solution method.

Table 11. The average gap in percentage for the IRP.

			CL-BC	AR-H2	C-M	G-BC	M-BC	V-M	AR-H3	S-M	VACS-M
Retailers	V	Size	E	M	M	E	E	M	M	M	M
50	2	20	2.57	1.76	3.59	0.11	0.24	1.06	3.89	0.81	2.35
	3	20	19.97	2.34	3.00	2.47	0.80	0.38	3.65	0.34	0.94
	4	20	–	2.67	2.38	3.91	0.79	0.17	3.31	1.16	−0.02
	5	20	–	4.25	2.84	5.55	0.64	0.05	3.40	1.54	−0.29
Average:			11.27	2.75	2.95	3.01	0.62	0.41	3.56	0.96	0.67
100	2	20	138.22	6.41	2.26	3.49	0.51	0.75	5.76	0.44	1.19
	3	20	216.39	6.30	2.90	12.68	1.07	0.64	4.68	0.14	1.22
	4	20	–	9.70	1.71	21.88	1.15	0.18	5.98	0.90	0.24
	5	20	–	8.20	2.00	27.57	1.53	0.08	4.99	1.57	−0.19
Average:			177.30	7.65	2.22	16.41	1.07	0.41	5.35	0.76	0.61
200	2	20	–	5.67	1.52	10.48	–	0.88	6.45	0.01	1.29
	3	20	–	9.10	2.26	19.90	–	0.65	9.93	0.07	0.74
	4	20	–	9.41	1.31	35.38	–	0.14	8.45	0.84	0.23
	5	20	–	9.56	0.94	46.87	–	0.19	7.68	1.20	−0.24
Average:			–	8.43	1.51	28.16	–	0.46	8.05	0.53	0.51
Total Average:			94.29	6.28	2.23	15.86	0.84	0.43	5.66	0.75	0.62

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, – = The instances are not solved by the solution method.

Table 12. The number of best-known solutions (BKSs) for the IRP.

			CL-BC	AR-H2	C-M	G-BC	M-BC	V-M	AR-H3	S-M	VACS-M
Retailers	V	Size	E	M	M	E	E	M	M	M	M
50	2	20	0	0	0	8	7	2	0	3	1 (1)
	3	20	0	0	0	0	3	6	0	9	3 (3)
	4	20	–	0	0	0	2	6	0	0	13 (12)
	5	20	–	0	0	0	0	8	0	0	12 (12)
Sum:			0	0	0	8	12	22	0	12	29 (28)
100	2	20	0	0	0	0	8	5	0	6	1 (1)
	3	20	0	0	0	0	3	4	0	10	3 (3)
	4	20	–	0	0	0	2	7	0	3	8 (8)
	5	20	–	0	0	0	0	10	0	1	9 (9)
Sum:			0	0	0	0	13	26	0	20	21 (21)
200	2	20	–	0	0	0	–	2	0	17	1 (1)
	3	20	–	0	0	0	–	4	0	15	1 (1)
	4	20	–	0	0	0	–	9	0	4	7 (7)
	5	20	–	0	0	0	–	5	0	1	14 (14)
Sum:			–	0	0	0	–	20	0	37	23 (23)
Total Sum:			0	0	0	8	25	68	0	69	73 (72)

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, – = The instances are not solved by the solution method.

Table 13. The average computing time in seconds for the IRP.

			CL-BC	AR-H2	C-M	G-BC	M-BC	V-M	AR-H3	S-M	VACS-M
Retailers	V	Size	E	M	M	E	E	M	M	M	M
50	2	20	86,400	5640	435	7200	7200	166	131	408	27
	3	20	86,400	5729	546	7200	7200	318	2840	3633	53
	4	20	–	5867	519	7200	7200	514	3543	3646	146
	5	20	–	5924	574	7200	6952	544	4837	3659	334
Average:			86,400	5790	519	7200	7138	385	2835	2836	140
100	2	20	86,400	2357	2406	7200	7200	270	93	426	56
	3	20	86,400	3690	2394	7200	7201	588	883	3316	90
	4	20	–	2705	2270	7200	7201	794	2980	3662	167
	5	20	–	3129	2513	7200	7200	1033	4989	3677	262
Average:			86,400	2970	2396	7200	7200	671	2236	2770	144
200	2	20	–	4201	14,128	7200	–	613	338	2723	216
	3	20	–	4201	9688	7200	–	963	534	6829	288
	4	20	–	4200	12,606	7200	–	1446	1316	7500	501
	5	20	–	4201	13,495	7200	–	1892	2483	7524	677
Average:			–	4201	12,480	7200	–	1229	1168	6144	421
Total Average:			86,400	4320	5131	7200	7169	762	2080	3917	235

Note: $V=$ Number of vehicles, E = Exact method, H = Heuristic, M = Matheuristic, – = The instances are not solved by the solution method.

Table 14. The reduction in solution quality, given in percentage, if different components of the matheuristic are removed.

Set	V	Size	No intensification phase	No diff. technique 1	No diff. technique 2	No diff. technique
A1-1	∞	10	0.06	0.03	0.00	0.04
A1-2	∞	10	0.00	0.01	0.00	0.01
A1-3	∞	10	0.16	0.00	2.45	2.44
A1-4	∞	10	0.04	0.10	0.00	0.45
A2-1	∞	10	0.03	0.02	0.00	0.02
A2-2	∞	10	0.01	0.00	0.00	0.00
A2-3	∞	10	0.14	0.03	1.49	1.41
A2-4	∞	10	0.07	0.05	0.00	0.05
Average			0.06	0.03	0.49	0.55
B1	5	30	0.36	0.31	0.03	0.35
B2	9	30	0.06	0.32	0.00	0.42
B3	13	30	0.07	0.38	0.02	0.38
Average			0.16	0.33	0.02	0.38
Total Average			0.07	0.11	0.14	0.26

Note: $V=$ Number of vehicles, diff. = differentiation.

Schenekemberg, C. M., C. T. Scarpin, J. E. Pecora Jr, T. A. Guimarães, and L. C. Coelho. 2021. “The Two-Echelon Production-Routing Problem.” European Journal of Operational Research 288: 436–449.

 Web of Science ®Google Scholar

Adulyasak, Y., J. F. Cordeau, and R. Jans. 2014a. “Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems.” INFORMS Journal on Computing 26: 103–120.

 Web of Science ®Google Scholar

Boudia, M., and C. Prins. 2009. “A Memetic Algorithm with Dynamic Population Management for an Integrated Production–Distribution Problem.” European Journal of Operational Research 195: 703–715.

 Web of Science ®Google Scholar

Adulyasak, Y., J. F. Cordeau, and R. Jans. 2014b. “Optimization-Based Adaptive Large Neighborhood Search for the Production Routing Problem.” Transportation Science 48: 20–45.

 Web of Science ®Google Scholar

Qiu, Y., L. Wang, X. Xu, X. Fang, and P. M. Pardalos. 2018. “A Variable Neighborhood Search Heuristic Algorithm for Production Routing Problems.” Applied Soft Computing 66: 311–318.

 Web of Science ®Google Scholar

Absi, N., C. Archetti, S. Dauzère-Pérès, and D. Feillet. 2015. “A Two-Phase Iterative Heuristic Approach for the Production Routing Problem.” Transportation Science 49: 784–795.

 Web of Science ®Google Scholar

Solyalı, O., and H. Süral. 2017. “A Multi-Phase Heuristic for the Production Routing Problem.” Computers & Operations Research 87: 114–124.

 Web of Science ®Google Scholar

Chitsaz, M., J. F. Cordeau, and R. Jans. 2019. “A Unified Decomposition Matheuristic for Assembly, Production, and Inventory Routing.” INFORMS Journal on Computing 31: 134–152.

 Web of Science ®Google Scholar

Li, Y., F. Chu, C. Chu, and Z. Zhu. 2019. “An Efficient Three-Level Heuristic for the Large-Scaled Multi-Product Production Routing Problem with Outsourcing.” European Journal of Operational Research 272: 914–927.

 Web of Science ®Google Scholar

Avci, M., and S. T. Yildiz. 2019. “A Matheuristic Solution Approach for the Production Routing Problem with Visit Spacing Policy.” European Journal of Operational Research 279: 572–588.

 Web of Science ®Google Scholar

Manousakis, E. G., G. A. Kasapidis, C. T. Kiranoudis, and E. E. Zachariadis. 2022. “An Infeasible Space Exploring Matheuristic for the Production Routing Problem.” European Journal of Operational Research 298: 478–495.

 Web of Science ®Google Scholar

Data availability statement

The data that support the findings of this study are openly available at http://axiomresearchproject.com/publications/.