Multi-depot bus schedule assignment with parking and maintenance constraints for intercity transportation over a planning period

Figures & data

Figure 1. Creating vehicle blocks from trips (taken from Árgilán et al. (2014)).

Figure 2. Illustration of the underlying model.

Table 1. Real input characteristics.

Vehicles	238
Garages	109
Maintenance locations	6
Average daily blocks	131

Table 2. Results for the real-life instances.

Depots	Weeks	s	Columns	Rows	Time (s)	Gap (%)
2	1	2	397 694	8 422	1 038	0.00
		3	591 051	11 026	114	0.00
		4	784 408	13 630	86	0.00
		5	977 765	16 234	84	0.00
		6	1 171 122	18 838	114	0.00
	2	2	799 652	16 232	5 520	0.00
		3	1 188 717	21 234	4 663	0.00
		4	1 577 782	26 236	2 207	0.00
		5	1 966 847	31 238	15 358	0.05
		6	2 355 912	36 240	29 345	0.00
	3	2	1 201 610	24 042	67 195	0.00
		3	1 786 383	31 442	48 705	0.00
		4	2 371 156	38 842	51 261	0.04
		5	2 955 929	46 242	77 546	0.05
		6	3 540 702	53 642	56 165	0.03
3	1	2	544 730	11 702	585	0.00
		3	808 860	15 487	128	0.00
		4	1 072 990	19 272	40	0.00
		5	1 337 120	23 057	39	0.00
		6	1 601 250	26 842	57	0.00
	2	2	1 094 569	22 467	3 395	0.00
		3	1 625 712	29 725	19 431	0.00
		4	2 156 855	36 983	25 304	0.04
		5	2 687 998	44 241	6 840	0.00
		6	3 219 141	51 499	21 640	0.00
	3	2	1 644 408	33 232	16 323	0.01
		3	2 442 564	43 963	22 957	0.04
		4	3 240 720	54 694	81 941	0.23
		5	4 038 876	65 425	79 146	0.37
		6	4 837 032	76 156	52 454	0.78

Table 3. Random input characteristics.

Trips	Average vehicles	Garages	Maintenance locations	Average daily blocks
100	51	30	2	17
500	219	40	3	55
1000	433	60	4	99

Table 4. Aggregated results for 900 random test runs.

			100 trips			500 trips			1000 trips
Depots	Weeks	s	Columns	Rows	Time (s)	Columns	Rows	Time (s)	Columns	Rows	Time (s)
2	1	2	15 787	1 135	0.79	67 641	2 423	2.37	177 985	4 044	7.35
		3	23 335	1 475	1.73	101 001	3 104	4.48	266 077	5 169	8.88
		4	30 883	1 814	1.35	134 361	3 785	3.99	354 169	6 293	8.98
		5	38 431	2 153	1.52	167 721	4 466	3.98	442 261	7 418	8.99
		6	45 979	2 493	2.04	201 081	5 148	3.12	530 353	8 543	10.28
	2	2	31 453	2 177	4.22	135 121	4 722	11.50	355 729	7 904	27.50
		3	46 519	2 826	7.84	201 801	6 044	42.04	531 853	10 093	329.77
		4	61 585	3 474	15.51	268 481	7 366	144.63	707 977	12 282	462.19
		5	76 651	4 123	39.01	335 161	8 689	268.54	884 101	14 472	683.01
		6	91 717	4 772	92.19	401 841	10 011	206.11	1 060 225	16 661	372.70
	3	2	47 119	3 219	7.48	202 601	7 020	31.31	533 473	11 763	127.11
		3	69 703	4 177	47.62	304 281	9 026	297.94	797 629	15 018	816.75
		4	92 287	5 153	225.45	402 601	10 948	10 115.95	1 059 321	18 273	25 449.56
		5	114 871	6 093	6 626.98	502 601	12 911	4 752.78	1 333 186	21 621	30 154.33
		6	137 455	7 051	6 682.53	602 601	14 875	6 374.63	1 598 791	24 889	51 144.84
3	1	2	23 431	1 208	0.76	90 713	2 521	2.97	235 609	4 259	10.51
		3	34 801	1 566	3.00	135 609	3 227	6.41	352 513	5 438	27.78
		4	46 171	1 923	2.94	180 505	3 932	9.76	469 417	6 617	32.84
		5	57 541	2 281	2.70	225 401	4 638	10.92	586 321	7 795	40.54
		6	68 911	2 638	3.48	270 297	5 344	6.01	703 225	8 974	13.11
	2	2	46 741	2 323	3.62	181 265	4 918	11.48	470 977	8 335	52.82
		3	69 451	3 008	18.60	271 017	6 289	51.55	704 725	10 632	527.44
		4	92 161	3 693	34.05	360 769	7 660	363.30	938 473	12 929	2 091.90
		5	114 871	4 378	61.79	450 521	9 032	533.76	1 172 221	15 226	2 843.32
		6	137 581	5 063	116.72	540 273	10 403	1 015.38	1 405 969	17 524	2 015.59
	3	2	70 051	3 437	5.88	271 817	7 314	39.74	706 345	12 410	125.09
		3	104 101	4 450	50.30	406 425	9 352	499.80	1 056 937	15 826	1 644.36
		4	138 151	5 463	619.36	541 033	11 389	2 531.34	1 402 041	19 197	41 684.79
		5	172 201	6 476	9 622.47	675 641	13 426	7 038.57	1 751 261	22 605	51 468.83
		6	206 251	7 488	3 401.35	810 249	15 463	25 688.33	2 100 481	26 014	97 058.60^a

aThe running time limit was relaxed for four test runs of this instance set in order to achieve optimal solutions in all 900 test cases. See Subsection 5.2 for details.

Table

$B$	Set of vehicle blocks
$D$	Set of depots
$G$	Set of garages
$M$	Set of maintenance locations
$N$	Set of all nodes
$E^{bs}$	Set of block starting edges
$E^{be}$	Set of block ending edges
$E^g$	Set of garage waiting edges
$E^{is}$	Set of inspection starting edges
$d_{i,0}$	The node representing vehicles of depot $i$ at the beginning of the planning period
$kd(i)$	Capacity of depot $i$
$kg(i)$	Capacity of garage $i$
$km(i)$	Capacity of maintenance location $i$

Árgilán, V., J. Balogh, J. Békési, B. Dávid, G. Galambos, M. Krész, and A. Tóth. 2014. “ Ütemezési feladatok az autóbuszos közösségi közlekedés operatív tervezésében: Egy áttekintés”, Alkalmazott Matematikai Lapok 31: 1-40. ISSN 0133–3399

 Google Scholar