Detailed computational result of the RCKESPP

A new approach for the resource constrained k-th shortest path problem

For the computational experiment, the well-known VRPTW instance set of Solomon [6] was used, as the previous RCESPP studies have done [1, 3, 4]. Each instance has a complete graph with 102 vertices including the origin and sink nodes. Each instance has a vehicle with capacity of 200. The instance set is classified as R, C, and RC depending on how the vertices are geographically located. The locations of the vertices are randomly distributed in Type R instances and clustered in Type C instances. In Type RC instances, some are distributed randomly whereas others are clustered. The instances are grouped depending on type as r101-r112, c101-c109, and rc101-rc108. The tightness of the time windows is the only difference among the same type instances. Vertex in any instance has its own coordination and prize . The travelling time from to was calculated as and the travelling cost is calculated as . This paper sets as integers from 0 to 20 to obtain a reasonable percentage of negative arcs. The integers are set as Righini and Salani [4] did. Computational tests were done on an Intel Dual core E7300 2.66GHZ 2.67GHZ PC with 4GB RAM.

To the best of our knowledge, the most recent algorithm for the RCKESPP was proposed by Shi [5]. His algorithm follows the procedure of algorithm of Lawler [2]. Thus, this paper compares the proposed algorithm with Lawler’s. Tables 1 and 2 compare Lawler’s and the proposed algorithms’ computational times and numbers of generated states for the instances when k is 2, 5, 10, and 20. The computational time is measured in seconds. The columns headed with Gap(%) give the proposed algorithm’s percentage of the improvement over Lawler’s. These tables show that the proposed algorithm consistently generates fewer states and thus consumes less computational time for every instance and k value. Figures 1 and 2 show how the number of generated states and the computational time change as increases, respectively. The figures compare Lawler’s and the proposed algorithm by setting k from 1 to 20 on the instance c104. Figure 1 indicates that Lawler’s algorithm generates more states as k increases, while the proposed one generates states consistently regardless of k. Figure 2 indicates that Lawler’s algorithm consumes more computational time as k increases, while the proposed one consumes almost the same time regardless of k. Figures 1 and 2 have similar shapes because the computational time of the DP algorithm highly depends on the number of generated states.

Table 1. Computational result for k = 2, 5

	k=2						k=5
	Lawler		New Algorithm		Gap (%)		Lawler		New Algorithm		Gap (%)
	time	states	time	states	time	states	time	states	time	states	time	states
c101	0.22	262015	0.05	51620	79.3	80.3	0.30	328115	0.05	51888	84.2	84.2
c102	1.53	1674557	0.27	292153	82.1	82.6	1.97	2238064	0.26	288195	86.6	87.1
c103	5.42	5208681	1.29	1034255	76.3	80.1	13.71	13655084	1.28	1027669	90.7	92.5
c104	14.31	11352655	3.58	2264392	75.0	80.1	24.12	20139051	3.73	2304822	84.5	88.6
c105	0.31	367544	0.06	71265	79.7	80.6	0.39	471589	0.07	71514	83.5	84.8
c106	0.41	502159	0.09	100467	78.0	80.0	0.50	611395	0.09	100752	81.7	83.5
c107	0.40	480488	0.09	97047	78.3	79.8	0.52	637315	0.09	97175	83.4	84.8
c108	0.72	877250	0.17	180971	76.8	79.4	1.47	1864824	0.16	185990	88.9	90.0
c109	1.26	1519472	0.27	309394	78.3	79.6	2.53	3177807	0.28	320461	89.0	89.9
r101	0.06	66944	0.02	20063	68.3	70.0	0.16	174187	0.02	20387	86.6	88.3
r102	11.40	3626432	2.09	938016	81.7	74.1	13.84	5065526	2.10	938592	84.8	81.5
r103	8.80	5412423	2.20	1195766	75.0	77.9	15.66	11033799	2.53	1301636	83.8	88.2
r104	35.32	11639745	17.01	4586566	51.8	60.6	40.27	22129546	8.01	3089736	80.1	86.0
r105	0.25	268513	0.06	55404	76.0	79.4	0.54	587717	0.06	55799	88.3	90.5
r106	14.28	4313228	3.49	1419126	75.5	67.1	20.98	7196699	4.43	1566986	78.9	78.2
r107	18.37	7645776	4.04	1863475	78.0	75.6	28.68	14166896	4.00	1854919	86.0	86.9
r108	22.13	10614957	4.61	2254591	79.2	78.8	28.20	16276837	10.26	3465735	63.6	78.7
r109	0.81	839422	0.18	160849	77.8	80.8	1.63	1816296	0.18	164546	88.8	90.9
r110	5.04	3185193	0.91	674064	81.9	78.8	9.06	7991178	0.92	680420	89.9	91.5
r111	36.20	6664411	3.88	1762656	89.3	73.6	38.01	11011212	3.91	1764017	89.7	84.0
r112	11.51	6618433	7.31	2714618	36.5	59.0	22.79	14307286	5.22	2278570	77.1	84.1
rc101	0.16	171470	0.04	40719	73.9	76.3	0.34	364195	0.04	40803	87.5	88.8
rc102	0.73	821774	0.17	164979	77.2	79.9	1.77	2026238	0.17	170627	90.5	91.6
rc103	2.53	2502612	0.49	454496	80.8	81.8	4.24	4720830	0.49	454972	88.6	90.4
rc104	32.02	9320068	1.86	1303477	94.2	86.0	33.66	11164378	1.57	1197120	95.3	89.3
rc105	0.43	473190	0.11	110540	74.1	76.6	0.99	1141481	0.11	110565	89.1	90.3
rc106	0.54	586291	0.14	131140	74.0	77.6	0.96	1111932	0.14	131497	85.5	88.2
rc107	1.62	1634032	0.45	402166	72.2	75.4	3.16	3363444	0.46	406271	85.6	87.9
rc108	3.15	3112749	0.82	717401	73.8	77.0	6.92	7309195	0.84	718232	87.9	90.2

Table 2. Computational result for k = 10, 20

	k=10						k=20
	Lawler		New Algorithm		Gap (%)		Lawler		New Algorithm		Gap (%)
	time	states	time	states	time	states	time	states	time	states	time	states
c101	0.44	485261	0.05	52668	89.0	89.1	0.58	713966	0.05	53603	91.2	92.5
c102	2.14	2515472	0.26	289265	87.6	88.5	3.29	4018492	0.27	291578	91.9	92.7
c103	18.52	18809416	1.28	1035057	93.1	94.5	21.83	23252746	1.30	1043985	94.0	95.5
c104	52.08	47250175	3.95	2386036	92.4	95.0	83.03	80406120	3.85	2355629	95.4	97.1
c105	0.81	990708	0.07	72480	91.9	92.7	1.08	1348727	0.07	74274	93.5	94.5
c106	0.71	888745	0.09	101630	86.8	88.6	1.01	1285671	0.09	102617	90.8	92.0
c107	0.92	1138227	0.09	98226	90.4	91.4	1.42	1791060	0.09	100349	93.5	94.4
c108	2.43	3139895	0.17	188067	93.2	94.0	3.06	4017208	0.17	190044	94.4	95.3
c109	4.53	5763260	0.29	327949	93.6	94.3	6.48	8428446	0.30	334841	95.4	96.0
r101	0.20	220868	0.02	20631	88.8	90.7	0.27	308245	0.02	21113	91.5	93.2
r102	22.09	10044289	2.10	940377	90.5	90.6	28.29	14080025	2.11	943007	92.5	93.3
r103	22.69	16937684	3.46	1560465	84.8	90.8	47.52	34124077	3.42	1559880	92.8	95.4
r104	60.28	38761765	10.12	3519272	83.2	90.9	137.14	67258510	11.46	3478336	91.6	94.8
r105	0.71	804350	0.06	56411	91.3	93.0	1.29	1488830	0.07	57934	94.9	96.1
r106	32.91	11726986	4.37	1569976	86.7	86.6	53.75	20178129	5.00	1652562	90.7	91.8
r107	43.81	28328004	4.02	1857682	90.8	93.4	64.43	42059268	4.67	2029027	92.8	95.2
r108	29.41	17564810	8.30	3098793	71.8	82.4	69.22	42265459	8.29	3104067	88.0	92.7
r109	3.08	3448253	0.19	169998	93.8	95.1	5.44	6153499	0.20	175407	96.3	97.1
r110	13.43	12803914	0.91	682379	93.2	94.7	18.85	18872901	0.90	679098	95.2	96.4
r111	40.88	12806004	4.63	1932727	88.7	84.9	42.23	15719756	5.54	2116709	86.9	86.5
r112	28.63	18875159	6.01	2465366	79.0	86.9	63.61	37552120	7.27	2710032	88.6	92.8
rc101	0.60	678727	0.05	41805	92.5	93.8	0.90	1052775	0.05	42887	94.7	95.9
rc102	2.75	3145387	0.17	171178	93.7	94.6	4.41	5217034	0.18	173211	96.0	96.7
rc103	5.38	6218635	0.49	456220	90.9	92.7	7.84	9202713	0.50	467826	93.6	94.9
rc104	34.92	12895802	1.71	1242992	95.1	90.4	39.97	18859015	1.96	1340840	95.1	92.9
rc105	1.60	1863337	0.11	112238	93.0	94.0	1.81	2134700	0.12	113400	93.6	94.7
rc106	1.53	1815310	0.14	131787	90.8	92.7	1.95	2374017	0.15	133691	92.5	94.4
rc107	4.97	5621602	0.46	406742	90.8	92.8	6.57	7717624	0.46	407187	93.0	94.7
rc108	12.87	13877100	0.87	746921	93.2	94.6	22.14	24324543	0.90	756113	95.9	96.9

Figure 1. Trend of the number of generated states as k increases (Instance c104)

Figure2. Trend of the computational time as k increases (Instance c104)

Reference

1. D. Feillet, P. Dejax, M. Gendreau and C. Gueguen, An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks 44 (2004), no. 3, 216-229.

2. E.L. Lawler, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem, Management Science 18 (1972), no. 7, 401-405.

3. G. Righini and M. Salani, Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization 3 (2006), no. 3, 255-273.

4. ---, New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks 51 (2008), no. 3, 155-170.

5. N. Shi, K constrained shortest path problem, IEEE Transactions on Automation Science and Engineering 7 (2010), no. 1, 15-23.

6. M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35 (1987), no. 2, 254-265.