Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem

Ahmed Tarajo Buba; Lai Soon Lee

doi:10.3934/naco.2018023

Article Contents

2018, Volume 8, Issue 3: 351-376. Doi: 10.3934/naco.2018023

This issue Previous Article Homotopy perturbation method and Chebyshev polynomials for solving a class of singular and hypersingular integral equations Next Article Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization

Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem

Ahmed Tarajo Buba^1, and
Lai Soon Lee^1,2, ,

1.
Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia
2.
Laboratory of Computational Statistics and Operations Research, Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia

* Corresponding author: Lai Soon LEE
* Corresponding author: Lai Soon LEE

Received: April 30, 2017

Revised: February 28, 2018

Published: June 2018

The first author is supported by FRGS2016 (01-01-16-1867FR)

Abstract Full Text(HTML) Figure(9) / Table(13) Related Papers Cited by

Abstract

The urban transit routing problem (UTRP) deals with public transport systems in determining a set of efficient transit routes on existing road networks to meet transit demands. The UTRP is a complex combinatorial optimization problem characterized with a large search space, multi-constraint, and multiobjective nature where the likelihood of generating infeasible route sets is high. In this paper, an improved sub-route reversal repair mechanism is proposed to deal with the infeasibility. A population-based metaheuristic, namely, Differential Evolution (DE) algorithm is then proposed to handle the multiobjective UTRP with the aim of devising an efficient transit route network that optimizes both passengers' and operators' costs. Computational experiments are performed on well-known benchmark instances to evaluate the effectiveness of the proposed repair mechanism and the DE algorithm. The computational results are reported to have better parameter values in most cases when compared to other approaches in the literature.

Keywords:

Mathematics Subject Classification: Primary: 90B06, 90B10; Secondary: 65K05, 68W99.

Citation:

Full Text(HTML)

Figure 1. A sample vector with 4 routes

Download: Full-size image PowerPoint slide

Figure 2. Mandl's Swiss Network

Download: Full-size image PowerPoint slide

Figure 3. Mumford Network

Download: Full-size image PowerPoint slide

Figure 4. Best Route Network for Operator and Passenger with 4 Routes (see, Table 4)

Download: Full-size image PowerPoint slide

Figure 5. Best Route Network for Operator and Passenger with 6 Routes (see, Table 4)

Download: Full-size image PowerPoint slide

Figure 6. Best Route Network for Operator and Passenger with 7 Routes (see, Table 4)

Download: Full-size image PowerPoint slide

Figure 7. Best Route Network for Operator and Passenger with 8 Routes (see, Table 4)

Download: Full-size image PowerPoint slide

Figure 8. Approximate Pareto Fronts achieved by the proposed DE for Mandl's Swiss Network

Download: Full-size image PowerPoint slide

Figure 9. Pareto Fronts achieved by the proposed DE for Mumford Network

Download: Full-size image PowerPoint slide

Table 3. Comparison results (passenger and operator) of Mandl's Swiss network

Number of Routes	Para-meters	Fan et al. (2009)		Mumford (2013)		Chew et al. (2013)		Proposed DE
Number of Routes	Para-meters	1	2	1	2	1	2	1	2
4	$d_{0}$	90.88	61.08	90.43	61.08	91.84	61.08	91.46	61.08
	$d_{1}$	8.35	36.61	9.57	36.61	8.16	36.61	8.54	36.61
	$d_{2}$	0.77	2.31	0.00	2.31	0.00	2.31	0.00	2.31
	$d_{un}$	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00
	$C_{p}$	10.65	13.88	10.57	13.88	10.50	13.88	10.80	13.88
	$C_{o}$	126	63	149	63	150	63	133	63
6	$d_{0}$	93.13	65.18	95.38	70.91	96.79	70.91	97.24	70.46
	$d_{1}$	6.29	30.38	4.36	25.50	3.21	25.50	2.76	24.34
	$d_{2}$	0.58	3.53	0.06	2.95	0.00	2.95	0.00	5.20
	$d_{un}$	0.00	0.90	0.00	0.64	0.00	0.64	0.00	0.00
	$C_{p}$	10.49	13.82	10.27	13.48	10.21	13.48	10.16	12.60
	$C_{o}$	148	63	221	63	224	63	223	63
7	$d_{0}$	92.55	64.42	96.47	65.13	98.01	70.65	97.37	68.96
	$d_{1}$	6.68	26.20	3.34	22.93	1.99	21.13	2.63	26.29
	$d_{2}$	0.77	8.16	0.19	10.34	0.00	7.13	0.00	3.92
	$d_{un}$	0.00	1.22	0.00	1.61	0.00	1.09	0.00	0.83
	$C_{p}$	10.44	14.13	10.22	14.25	10.16	13.76	10.21	13.46
	$C_{o}$	166	63	264	63	239	63	235	63
8	$d_{0}$	91.33	55.17	97.56	57.93	99.04	61.91	98.20	60.76
	$d_{1}$	8.67	21.97	2.31	31.92	0.96	29.67	1.80	25.63
	$d_{2}$	0.00	18.11	0.13	9.70	0.00	6.87	0.00	10.34
	$d_{un}$	0.00	4.75	0.00	0.45	0.00	1.54	0.00	3.26
	$C_{p}$	10.45	15.45	10.17	14.45	10.11	14.22	10.31	14.78
	$C_{o}$	245	63	291	63	256	63	244	63
Note: 1. best results for passenger 2. best results for operator

| Show Table

DownLoad: CSV

Table 1. The parameters of benchmark instances

Network	Nodes	Links	Routes	Min-Max Nodes	Demand	$LB_{Cp}$	$LB_{Co}$
Mandl	15	21	4, 6, 7, 8	2 - 8	15,570	10.0058	63
Mumford0	30	90	12	2 - 15	342,160	13.0121	94
Mumford1	70	210	15	10 - 30	1,926,170	19.2695	345
Mumford2	110	385	56	10 - 22	4,847,900	22.1689	864
Mumford3	127	425	60	12 - 25	6,394,950	24.7453	982

| Show Table

DownLoad: CSV

Table 2. The comparison of feasible route sets repaired by the four repair mechanisms

Case	Number of Routes	Repair Mechanism	Average	Minimum	Maximum	CPU Time (sec)
Ⅰ	4	TR	47	34	68	0.013
		MSC	53	39	69	0.052
		SRR	56	47	68	0.040
		iSRR	79	44	86	0.031
Ⅱ	6	TR	149	133	170	0.029
		MSC	206	193	220	0.490
		SRR	169	157	181	0.032
		iSRR	232	198	254	0.023
Ⅲ	7	TR	201	184	219	0.029
		MSC	293	267	317	0.066
		SRR	223	210	234	0.025
		iSRR	312	296	335	0.029
Ⅳ	8	TR	231	207	250	0.02
		MSC	356	319	376	0.042
		SRR	265	242	284	0.025
		iSRR	358	324	382	0.004

| Show Table

DownLoad: CSV

Table 4. Best route sets constructed by the proposed DE algorithm for Mandl's Swiss network

Case	Routes	Best route sets for Passenger	Best route sets for Operator
Ⅰ	4	0 - 1 - 2 - 5 - 7 - 14 - 8	14 - 8
		4 - 3 - 5 - 7 - 14 - 6 - 9 - 10	4 - 3 – 1 – 0
		0 – 1 - 4 - 3 - 5 - 7 - 9 - 6	10 - 9 - 6 - 14 - 7 - 5 - 2 - 1
		9 - 7 - 5 - 3 - 11 - 10 - 12 - 13	11 - 10 - 12 - 13
Ⅱ	6	8 - 14 - 7 - 9 - 10 - 11 - 3 - 4	11 - 3
		4 - 3 - 1 - 2 - 5 - 7 - 14 - 8	13 - 12 - 10 - 9
		14 - 6 - 9 - 7 - 5 - 3 - 1 - 0	9 - 6 - 14 - 7 - 5 - 2 - 1 - 3
		8 - 14 - 6 - 9 - 7 - 5 - 2 - 1	1 - 0
		13 - 12 - 10 - 9 - 7 - 5 - 14 - 8	8 - 14
		12 - 10 - 11 - 3 - 5 - 2 - 1 - 0	3 - 4
Ⅲ	7	1 - 4 - 3 - 5 – 7 - 9 - 13 - 12	0 - 1 - 2 - 5 - 7 - 14 - 6 - 9
		0 - 1 - 2 - 5 - 3 - 11 - 10 - 9	3 - 5
		1 - 2 - 5 - 7 - 9 - 10 - 12 - 13	4 – 3 - 1
		9 - 6 - 14 - 7 - 5 - 2 - 1 - 0	10 - 11
		0 - 1 - 4 - 3 - 5 - 7 - 14 - 8	14 – 8
		8 – 14 - 6 - 9 - 13 - 12 - 10 - 11	10 - 9
		8 - 14 - 7 – 5 - 2 - 1 - 3 - 11	10 - 12 - 13
Ⅳ	8	0 - 1 - 2 - 5 - 14 - 7	1 - 3
		0 – 1 - 4 - 3 - 5 - 7 - 14 - 8	10 - 11
		0 – 1 - 2 - 5 - 7 - 9 - 6 - 14	3 - 5 - 7 - 14 - 6 - 9 - 10 - 12
		11 - 3 - 5 - 7 - 14 - 6 - 9	14 - 8
		0 – 1 - 4 - 3 - 5 - 7 - 9 - 10	0 - 1
		13 – 12 - 10 - 9 - 6 - 14 - 8	3 - 4
		12 – 10 - 11 - 3 - 5 - 2 - 1 - 0	5 - 2
		13 – 12 - 10 - 9 - 6 - 14 - 7 - 5	12 - 13

| Show Table

DownLoad: CSV

Table 5. Comparison results (passenger and operator) of Large Mumford networks

Instances	Parameters	Mumford (2013)		Proposed DE
Instances	Parameters	1	2	1	2
Mumford0	$d_{0}$	63.20	18.42	65.41	16.99
	$d_{1}$	35.82	23.40	34.24	30.72
	$d_{2}$	0.98	20.78	0.35	28.92
	$d_{un}$	0.00	37.40	0.00	23.38
	$C_{p}$	16.05	32.40	15.27	33.41
	$C_{o}$	759	111	673	107
Mumford1	$d_{0}$	36.6	16.35	38.77	22.39
	$d_{1}$	52.42	29.06	54.23	40.57
	$d_{2}$	10.71	29.92	5.12	34.33
	$d_{un}$	0.26	24.66	1.88	2.71
	$C_{p}$	24.79	34.69	23.16	31.15
	$C_{o}$	2038	568	1955	567
Mumford2	$d_{0}$	30.92	13.76	31.47	15.32
	$d_{1}$	51.29	27.69	58.23	29.31
	$d_{2}$	16.36	29.53	9.60	31.08
	$d_{un}$	1.44	29.02	0.70	24.29
	$C_{p}$	28.65	36.54	27.28	34.52
	$C_{o}$	5632	2244	5268	2305
Mumford3	$d_{0}$	27.46	16.71	28.12	25.42
	$d_{1}$	50.97	33.69	54.35	41.26
	$d_{2}$	18.76	29.18	16.84	24.91
	$d_{un}$	2.81	20.42	0.69	8.41
	$C_{p}$	31.44	36.92	30.16	34.81
	$C_{o}$	6665	2830	6547	2732
Note: 1. best results for passenger 2. best results for operator

| Show Table

DownLoad: CSV

Table A1. Best route sets for the operator constructed by the proposed DE algorithm for Mumford0 network

Routes	Sequence of Routes
1	1-23-14-11-25- 0-17-22
2	9 - 1 - 3
3	0-12-8-26
4	22-18-13-6
5	19-18
6	25-28-16-27-2-29-15-10
7	20-14
8	1 - 3
9	3-24-4
10	21 - 10
11	20 - 7
12	5 - 21

| Show Table

DownLoad: CSV

Table A2. Best route sets for the passenger constructed by the proposed DE algorithm for Mumford0 network

Routes	Sequence of Routes
1	20-24-7-28-17-11-25-22-18-19-12-8-26-0-13
2	12-19-22-0-25-28-7-4-24-14-9-1-3-23-20
3	12-19-8-26-0-18-17-11-14-9-3-1-23-20-24
4	29-2-27-16-7-14-24-3-11-25-22-18-19-12-17
5	27-10-15-21-5-6-13-18-12-19-22-17-0-26-8
6	3-1-4-23-20-14-11-25-0-19-17-18-13-6-15
7	19-8-26-0 -8-17-11-14-24-3-1-9-23-20-7
8	26-0-22-19-12-18-17-28-16-10-29-2-15-21-5
9	19-8-26-0-22-18-12-17-28-25-11-14-24-20-23
10	0-13-6-2-15-16-7-14-24-3-23-2-4-1-9
11	24-4-20-23-9-3-1-14-7-25-22-0-13-18-17
12	13-18-12-17-19-0-25-11-14-23-9-1-24-4-7

| Show Table

DownLoad: CSV

Table A3. Best route sets for the operator constructed by the proposed DE algorithm for Mumford1 network

Routes	Sequence of Routes
1	22-33- 43-13-20-10-59-68-11-31
2	18-32-37-67-27-25-4-40-46-7
3	30-42-62-15-49-11-31-9-16-10
4	21-63-30-24-42-15-49-26-16-10
5	67-65-37-5-54-19-36-45-34-35
6	28-56-8-26-49-1-16-55-20-10
7	47-40-46-7-53-4-12-25-34-35
8	12-41-34-35-6-21-63-24-30-26
9	12-41-34-51-56-6-21-63-24-30
10	57-25-34-58-64-52-20-17-50-23
11	22-33-13-43-61-44- 60-14-2-50
12	50-0-2-23-3-66-38-36-54-18
13	15- 49-1-31- 9-16-10-52-64-58
14	6-55-52- 64-35-51-8-10-17-50
15	39-48-66-29-69-19-54-5-37-65

| Show Table

DownLoad: CSV

Table A4. Best route sets for the passenger constructed by the proposed DE algorithm for Mumford1 network

Routes	Sequence of Routes
1	48-69-38- 66-19- 65-54-5-37- 67-27-25-57-34-35-6-47-53-40-46-7-4-12- 41-58-33-50-2-0-23
2	59-1-31-11- 68- 9- 49- 62- 42-30-26-16-10-17-50-2-0-69-48-29-3-66-18-65-67-27-12- 40-53-7
3	27-25-34-51-35-58-64-52-20-55-8-26- 49-15-30-42-62-24-21- 6- 47-7- 46-40- 4-12-41-36-38-69
4	63-24-21-30-15-49-9-11-1-16-55-20-10-28-56-51-57-58-33-43-61-60-44-14-2-50-23-3-48-29
5	27-25-34-51-35-57-41-58-64-52-20-43-13-50-0-2-14-61-44-60-17-10-8-26-49-15-30-42-62-21
6	5-8-34-35-57-41-51-8-56-28-8-26-62-15-49-1- 59-17-50-23-3-48-29-19-54-65-67-27-12-40-53
7	45-36-38-69-29-19-18-54-5-65-37-32-39-48-3-23- 0-50-2-14-44-60-61-43-13-22-33-20-10-16
8	57-58-64-52-55-10-28-8-56-6-47-7-46-40-4-25-34-51-41-36-54-18-39-48-66-19-69-0-50-33
9	18-65-54-5-67-27-12-41-34-45-36-38-66-29-69-23-0-50-13-43-61-60-44-17-55-8-52-64-51-56
10	26-8-51-64-52-55-16-10-28-56-6-47-53-7-4-25-34-58-33-50-2-14-61-43-13-22-19-3-66-69
11	52-20-17-43-13-33-58-64-35-41-27-25-34-45-22-36-54-19-69-0-50-23-3-48-39-65-32-18-66
12	49-1-16-10-59-68-9-31-11-15-62-42-24-63-6-35-41-36-19-66-48-3-38-69-23-50-17-55-8-52
13	10-52-64-58-57-25-12-27-67-37-18-66-3-29-48-39-65-32-54-38-69-23-50-17-61-60-44-14-2-0
14	25-4-7-46-40-47-6-56-51-58-33-43-61-60-44-14-2-23-29-66-19-65-37-5-54-36-45-34-41-27
15	49-15-30-24-62-26-1-9-68-11-59-17-43-13-33-58-64-35-41-34-57-51-8-55-20-10-28-56-6-21

| Show Table

DownLoad: CSV

Table A5. Best route sets for the operator constructed by the proposed DE algorithm for Mumford2 network

Routes	Sequence of Routes
1	85-54-34-35-91-52-100-18-9-19
2	17-50-32-95-20-68-21-13-32-59
3	47-41-16-103-7-52-89-11-79-72
4	31-24-85-94-101-55-87-56-39-65
5	102-71-51-46-86-28-21-32-17-20
6	77-4-107-5-11-89-96-42-106-57
7	36-72-108-4-107-77-5-42-89-11-106-73
8	77-4-108-79-72-44-82-99-76-31
9	27-17-39-55-80-63-12-74-47-103
10	20-32-50-68-59-27-94-83-35-49
11	24-6-94-105-27-32-13-21-86-28
12	34-54-22-3-93-100-52-10-40-7
13	15-35-34-66-18-92-72-108-36-64
14	64-36-4-107-77-5-11-109-89-42
15	109-64-96-64-92-9-3-81-94-105
16	77-5-107-36-48-79-73-106-57-37
17	101-94-83-15-2-63-45-53-90-49
18	30-44-43-72-79-73-106-57-40-10
19	3-22-54-85-66-15-83-35-8-90
20	15-35-49-52-89-106-42-57-10-37
21	56-0-78-17-65-61-1-97-58-47
22	0-97-80-55-39-65-61-1-0-87
23	39-56-61-65-78-95-50-20-68-75
24	17-65-39-87-45-53-12-38-80-63
25	58-80-87-56-1-97-0-65-78-17
26	25-84-37-40-57-10-70-104-7-49
27	105-81-6-66-34-35-8-62-12-8
28	47-41-16-60-12-8-63-55-39-78
29	84-70-41-104-40-37-7-57-42-96
30	34-54-3-9-93-98-67-18-66-15
31	91-62-90-53-8-12-41-60-47-16
32	74-58-80-63-2-45-38-53-8-49
33	20-32-50-95-78-65-61-1-87-45
34	77-107-108-79-64-92-9-19-85-3
35	102-14-69-99-82-23-31-71-88-51
36	109-64-89-106-11-42-5-36-107-77
37	17-32-21-86-51-71-31-76-33-99
38	58-80-63-53-90-91-52-10-57-7
39	60-41-70-104-37-7-49-90-8-12
40	67-98-18-93-9-92-44-43-29-26
41	85-22-3-81-6-24-31-23-82-19
42	51-71-102-76-33-31-24-6-54-22
43	24-31-76-14-69-99-82-26-43-30
44	90-8-63-53-62-12-16-41-74-38
45	34-54-3-81-6-24-31-71-102-88
46	101-27-32-20-75-50-13-28-86-24
47	108-36-48-44-72-26-29-43-30-69
48	17-50-75-68-13-32-59-27-95-20
49	62-90-91-35-34-3-85-24-22-66
50	24-6-54-85-66-15-83-2-35-90
51	48-36-108-4-77-5-42-73-109-89
52	65-78-17-20-50-68-59-28-46-21
53	81-6-94-2-63-8-90-35-49-91
54	36-64-73-89-52-49-35-34-18-93
55	17-39-55-45-2-94-83-35-90-91
56	36-72-108-4-107-77-5-11-73-96

| Show Table

DownLoad: CSV

Table A6. Best route sets for the passenger constructed by the proposed DE algorithm for Mumford2 network

Routes	Sequence of Routes
1	96-11-73-89-42-5-36-107-48-79-64-92-9-66-18-3-98-67-100-93-34
2	90-53-38-12-62-91-52-100-18-3-98-93-67-92-72-44-82-19-33-14-31
3	77-5-36-108-4-107-48-92-64-109-11-73-96-42-89-52-100-18-9-19-102-88
4	26-72-36-79-108-4-107-5-11-106-57-37-104-7-49-35-15-54-6-86-46-21
5	26-30-44-72-36-48-108-4-77-5-11-73-64-89-52-91-62-12-60-58-80
6	21-59-27-17-50-32-95-68-13-28-86-81-3-22-85-19-82-23-9-92-44-72
7	88-71-51-31-24-6-22-3-34-18-67-100-93-35-8-90-62-103-70-10
8	77-5-11-73-109-89-96-64-36-79-108-4-107-48-92-44-82-19-24-86-28-46
9	67-100-93-98-18-3-54-24-19-85-22-66-9-92-72-79-73-96-42-11-89-52
10	84-25-70-103-12-41-74-58-38-80-55-87-39-0-61-65-56-17-50-32-95-78
11	21-32-13-68-50-17-39-55-63-12-103-70-7-52-100-18-9-19-82-44-48-107
12	29-26-44-92-72-36-79-73-89-52-49-90-91-8-53-38-87-55-45-2-35-15
13	69-99-33-19-82-44-72-92-18-66-34-35-91-100-52-10-40-57-106-73-79
14	50-13-21-86-81-105-83-3-9-92-64-36-4-107-77-5-11-109-89-42-96-73
15	35-15-83-34-54-6-81-86-28-13-68-17-27-94-101-55-87-56-39-65-61
16	74-60-47-58-97-80-38-87-56-17-78-39-65-50-20-75-68-95-59-27-105-94
17	79-64-73-109-11-106-89-96-42-57-10-70-84-104-40-25-7-49-35-83-94-27
18	24-85-22-3-67-18-93-9-19-23-82-33-31-51-46-21-32-17-39-55-63-12
19	74-60-47-58-97-80-38-12-63-53-62-90-49-52-89-64-36-4-107-77
20	84-7-10-70-104-25-40-37-57-42-106-73-89-109-11-79-36-108-72-92-18-66
21	90-53-8-91-35-2-15-34-93-67-3-66-18-9-92-44-82-33-31-51-46-21
22	83-105-94-6-81-85-24-86-28-21-27-101-55-87-56-65-50-75-17-78-0-1
23	28-13-50-65-56-0-87-97-80-45-38-58-47-103-12-63-55-39-17-50-68
24	96-64-109-11-5-42-57-106-73-89-52-91-90-35-93-98-18-9-19-33-76
25	89-42-106-57-37-104-7-49-35-15-54-6-86-24-19-82-44-72-79
26	22-85-54-6-66-18-9-19-3-81-86-51-71-88-102-76-69-30-26-82-33-31
27	96-89-109-73-42-106-11-64-79-48-92-67-3-93-100-18-9-19-33-14-102
28	23-82-26-72-92-48-108-5-77-4-36-64-89-52-49-90-8-53-38-63-80-58
29	101-55-39-87-80-0-56-65-78-17-95-59-21-86-51-102-76-69-30-43-29-26
30	22-85-54-6-66-18-100-93-98-67-3-34-35-90-8-62-12-38-80-55-101-27
31	62-53-38-58-80-55-39-78-95-17-27-94-101-55-87-56-39-65-61
32	36-48-92-44-82-23-9-3-83-2-45-87-38-53-90-49-52-89-64-109-73-89
33	106-11-73-96-42-5-77-4-107-108-48-92-64-79-72-43-44-82-19-24-86-21
34	62-91-52-100-18-98-93-35-34-66-6-24-31-23-9-19-102-88-71-51-46
35	47-62-103-12-38-58-97-1-61-56-65-78-95-27-94-85-19-82-26-30-44
36	50-95-78-17-68-59-27-94-83-35-49-52-89-106-73-79-72-44-82-99-76
37	9-3-66-85-22-3-93-100-52-10-70-16-74-58-97-0-61-1-87-38-53
38	36-48-92-67-3-15-83-34-66-18-93-9-19-33-76-31-24-6-94-101-55-39
39	66-85-6-81-86-46-28-21-13-32-20-95-17-27-94-105-83-35-8-62-91
40	107-77-4-36-5-42-11-96-73-106-57-40-7-103-12-63-55-39-17-50-68
41	100-18-67-93-9-92-72-36-4-77-5-107-108-79-48-44-30-43-26-82-19-24
42	62-91-52-100-18-98-93-35-34-66-6-24-54-3-19-33-99-69-30-29-43
43	83-15-35-90-49-91-62-12-103-70-10-52-100-93-3-22-85-66-34-35
44	2-83-3-34-54-66-6-94-105-81-86-46-21-68-20-32-13-28-59-95-27-101
45	86-6-54-22-3-9-19-23-33-99-69-14-76-31-24-85-94-101-55-39-87-1-97
46	69-43-29-26-44-92-18-9-19-102-88-71-51-86-21-59-95-78-0-1
47	52-100-91-8-35-15-2-34-66-3-67-98-93-9-18-92-64-109-73-79-72
48	24-6-54-22-66-85-3-98-67-92-44-43-69-30-26-82-33-31-51-46-21-32
49	57-42-96-11-79-36-5-107-77-4-108-48-44-26-82-19-24-86-21-13-32-59
50	75-68-21-32-50-65-56-61-0-80-63-45-2-15-18-92-48-107-77-5-11-89
51	17-68-59-32-95-27-94-83-35-15-3-9-18-100-52-10-70-41-12-63-55-39
52	38-80-45-87-56-61-0-1-97-58-60-12-62-91-52-89-64-36-107-48-72-26
53	71-88-51-102-33-99-14-69-30-29-43-72-79-73-106-57-37-104-41-12-63-55
54	15-34-54-85-3-93-67-98-18-66-22-31-23-9-19-102-88-51-86-21-27-101
55	33-19-3-34-66-93-100-52-89-109-73-11-42-96-64-92-9-3-81-94-105-27
56	41-16-47-74-58-80-55-87-0-1-61-65-39-55-101-94-81-85-24-19-33-76

| Show Table

DownLoad: CSV

Table A7. Best route sets for the operator constructed by the proposed DE algorithm for Mumford3 network

Routes	Sequence of Routes
1	122-94-27-118-46-11-0-101-26-126-92-85-20-50-76-19-13-83
2	29-36-24-87-61-102-108-115-3-96-78-114-23-2-37
3	99-48-79-0-7-40-44-82-88-39
4	35-91-82-95-13-83-50-92-76-20
5	105-42-89-31-39-88-82-40-50-76
6	66-53-23-2-48-126-92-83-13-19
7	38-25-88-121-125-91-82-40-50-20
8	81-9-66-80-29-122-52-51-54-30
9	81-27-94-29-5-36-58-104-43-28
10	107-12-3-96-71-100-14-106-108-102
11	82-116-101-0-48-2-49-72-9-5
12	105-42-43-104-59-113-90-103-98-17
13	27-94-122-29-36-80-5-24-87-110-68-34-56
14	105-42-89-31-39-88-82-40-50-13
15	116-120-7-11-0-77-67-1-27-29
16	105-58-36-5-24-117-86-109-69-10-4-18
17	81-94-29-9-66-53-23-2-79-0
18	44-65-50-83-13-95-123-35-91-25-38-54-51-47
19	85-20-92-126-48-79-0-101-88-121
20	60-55-99-73-6-112-62-16-114-78-71-100-14-108-61-106
21	81-29-80-63-105-42-28-103-43-104-18-10
22	15-3-96-100-12-78-114-74-23-72-124
23	31-38-52-27-1-77-67-46-39-25
24	74-49-124-70-66-9-29-5-24-117
25	48-26-93-44-40-65-116-82-88-39
26	122-94-29-27-67-11-79-48-97-2
27	102-108-115-106-61-53-23-2-48-73
28	92-76-20-85-75-60-73-6-32-45
29	83-13-95-123-35-91-25-38-54-51
30	98-42-104-105-63-36-5-24-87-61-115-3-12-56
31	38-31-54-51-52-118-27-122-29-80-66-124-9
32	23-2-11-1-118-52-51-47-31-54
33	57-21-8-119-22-30-41-33-31-38-52-122
34	99-48-79-2-74-66-80-5-24-86
35	84-68-3-71-96-78-100-14-61-102
36	102-87-84-68-34-56-15-12-3-115-61-14-72-66
37	81-27-29-94-122-52-51-54-30-38
38	72-124-70-66-9-80-63-105-104-18-69-103-109-10-86
39	43-105-104-59-89-31-38-25-91-35
40	110-84-68-56-15-12-107-3-100-14
41	94-29-36-5-63-105-42-98-90-17
42	81-1-67-11-0-120-44-40-65-95
43	9-29-80-66-74-114-78-3-56-34
44	2-79-11-46-39-25-41-8-35-21
45	103-28-64-111-69-10-109-4-43-90-113-42
46	97-79-48-2-23-53-61-87-84-110
47	66-70-72-49-2-79-0-101-88-91
48	81-27-94-122-52-51-54-30-31-39
49	43-90-59-42-104-18-109-10-86-117-24-5-58-105
50	9-29-80-66-74-114-2-11-46-39
51	84-87-110-68-12-107-15-3-71-96-78-114-74-37-79-11-7-101-26
52	0-48-79-2-49-66-80-29-122-52
53	111-64-4-18-103-109-43-17-89-52
54	122-94-29-36-5-58-104-59-113-90
55	27-81-67-46-39-31-54-51-47-31
56	0-48-79-2-49-72-9-63-105-43
57	31-39-88-82-40-92-76-20-19-85
58	98-113-59-90-103-69-10-18-117-86
59	55-60-112-6-45-73-126-48-0-77-1-118
60	109-86-117-18-10-4-43-42-89-31

| Show Table

DownLoad: CSV

Table A8. Best route sets for the passenger constructed by the proposed DE algorithm for Mumford3 network

Routes	Sequence of Routes
1	23-114-16-62-112-6-73-48-26-7-40-82-44-93-88-39-46-1-118-27-29-5-24-87-110
2	27-118-67-81-80-70-72-74-2-23-37-97-11-7-40-50-13-19-85-75-20-32-60-73-48
3	12-3-78-114-74-23-37-2-11-46-39-30-22-21-35-91-25-38-31-89-59-104-58-63-5
4	46-1-11-2-74-49-66-14-100-12-56-15-3-78-114-16-55-60-32-20-85-19-13-83-92
5	57-8-21-125-22-41-30-39-46-11-2-74-23-53-61-108-102-24-5-63-36-9-80-81-67
6	17-98-113-89-31-39-88-93-44-40-95-65-50-20-19-32-45-60-6-73-126-92-76-85-75
7	41-33-54-31-89-59-104-43-105-63-80-66-74-114-16-112-60-73-48-2-23-53-61-102-87
8	13-92-85-75-60-55-45-73-48-2-49-72-9-63-105-43-69-10-86-24-102-61-14-100-78
9	102-106-115-61-14-100-71-3-96-78-114-23-37-74-2-79-0-120-65-101-88-82-40-92-85
10	29-81-94-122-52-27-67-46-118-1-11-0-48-73-60-75-20-50-40-82-91-125-22-8-21
11	63-36-80-66-49-124-23-72-9-5-24-102-61-87-84-68-56-12-107-3-96-100-71-78-114
12	86-10-69-111-28-64-98-90-103-43-42-89-31-39-88-82-40-50-76-20-75-85-19-13-83
13	27-94-122-29-36-80-5-24-87-110-68-34-56-3-78-114-2-79-0-101-88-121-125-123-91
14	111-64-103-69-109-10-18-104-58-63-9-72-49-2-97-48-79-11-67-27-29-5-24-87-110
15	70-9-81-27-1-11-2-74-23-53-61-106-108-102-24-5-29-122-52-51-54-30-31-39-88
16	102-24-5-29-27-1-46-39-25-41-57-22-125-21-8-35-91-121-88-101-7-120-116-93
17	63-36-9-72-23-37-74-114-2-97-0-48-26-101-88-125-21-119-22-30-39-46-11-7-65
18	35-8-22-119-21-125-121-25-91-123-95-65-7-11-2-114-78-12-100-14-66-80-29-94-81
19	39-46-11-2-23-53-14-106-108-61-102-87-110-84-56-15-107-3-78-71-96-100-12-68-34
20	70-72-124-49-2-74-66-9-63-80-36-5-29-122-27-1-67-11-77-0-120-26-7-40-50
21	9-72-66-53-23-114-2-11-26-7-101-120-116-95 40 44 82 65 50 76 85 75 20 32 126
22	62-16-55-6-73-48-97-2-23-74-72-66-14-108-115-3-78-71-96-100-12-56-15-107
23	74-49-23-72-66-70-9-5-24-36-29-27-67-46-118-122-52-38-30-22-119-8-41-25-88
24	105-58-63-36-24-102-61-115-106-14-108-87-84-110-68-56-15-107-3-96-100-12-78-114-2
25	47-51-89-113-59-42-104-43-105-63-80-66-74-114-16-112-60-73-48-2-23-53-61-102-87
26	96-71-78-12-68-84-56-3-100-14-61-87-106-115-108-102-24-5-58-104-43-98-42-89-31
27	102-87-84-68-34-56-15-12-3-115- 61-14-72-66-53-23-114-16-62-112-6-73-48-26-101
28	23-72-124-66-9-80-63-105-58-104-18-117-24-87-110-68-3-78-114-16-55-60-32-20-85
29	107-15-3-96-71-78-114-2-37-97-0-7-11-1-81-80-66-14-100-12-56-34-68-84-87
30	1-77-11-2-37-79-48-26-120-65-116-50-83-13-92-20-32-60-55-16-114-78-3-68-110
31	56-34-68-84-110-87-106-108-61-102-24-117-86-18-69-43-98-113-90-17-42-104-58-36-5
32	79-37-74-114-78-71-100-12-68-34-56-15-3-115-61-102-24-5-58-104-43-98-42-89-31
33	82-91-25-39-46-118-1-11-0-77-67-27-52-51-89-113-17-59-90-42-43-98-64-103-28
34	56-34-68-12-107-15-3-100-14-72-70-9-36-80-81-122-27-1-11-0-120-26-7-40-50
35	33-38-25-91-121-88-101-93-7-26-40-82-116-44-95-123-35-8-119-22-30-39-46-11-2
36	43-90-59-113-98-103-4-10-117-24-5-58-63-80-66-124-72-23-37-74-49-2-48-73-60
37	7-93-120-116-40-44-65-95-13-76-85-19-32-75-60-73-48-0-11-1-118-52-89-17-64
38	107-3-56-15-12-78-71-100-14-108-87-106-115-61-102-24-36-9-72-66-53-23-2-79-0
39	7-0-48-79-2-23-53-61-87-110-68-3-78-114-16-55-60-32-20-85-92-40-82-88-39
40	9-72-66-53-23-114-2-11-26-7-101-120-116-50-83-92-76-85-19-32-60-6-73-48-126
41	117-10-86-24-5-9-72-66-53-23-114-78-96-71-100-14-106-87-108-115-3-107-15-56-34
42	32-75-60-73-48-0-11-1-118-52-89-17-98-90-42-104-58-63-80-70-72-49-66-9-124
43	107-3-71-78-100-14-72-23-53-61-108-115-106-102-24-5-9-63-58-104-59-17-89-31-39
44	41-57-22-125-121-25-88-101-116-82-65-40-26-120-7-0-97-37-79-48-2-11-46-39-30
45	29-122-27-118-52-38-39-88-101-93-116-82-40-92-85-19-13-50-20-75-60-55-99-48-0
46	5-80-63-36-29-81-9-124-49-72-70-66-14-100-3-107-12-56-68-110-84-87-61-115-108
47	5-63-9-29-81-1-77-11-2-97-37-23-74-49-124-70-80-36-24-117-10-69-103-111-28
48	29-122-27-118-52-38-39-88-101-93-116-82-65-7-0-11-1-81-80-63-58-104-59-89-31
49	95-116-93-101-88-121-25-38-52-122-27-67-1-46-11-79-48-0-97-37-23-53-66-14-100
50	124-23-53-14-66-70-80-9-63-58-36-29-81-27-1-11-2-74-114-78-3-56-34-68-12
51	40-50-76-19-20-75-60-112-55-45-6-73-99-48-0-77-1-81-80-63-58-104-59-89-31
52	81-122-29-27-1-67-46-11-77-0-97-37-23-114-74-72-9-36-24-86-10-69-103-4-43
53	62-16-55-60-45-112-32-19-85-75-20-92-126-48-0-101-116-82-95-65-7-11-2-114-78
54	27-29-5-58-105-63-9-124-66-72-74-2-114-78-12-107-3-100-14-53-61-87-84-110-68
55	66-53-23-114-16-55-112-45-6-73-99-48-2-49-72-9-5-24-117-18-10-86-109-4-64
56	8-22-125-123-35-91-88-101-0-79-2-114-78-3-15-56-34-68-110-84-87-61-14-108-106
57	107-15-12-78-96-71-3-56-68-84-87-106-115-108-102-61-14-53-23-2-11-46-39-30-22
58	84-110-68-34-56-3-71-78-114-74-49-23-2-79-0-101-88-91-123-125-22-8-41-25-38
59	78-96-3-56-15-12-100-14-108-61-115-106-87-102-24-5-80-70-9-72-49-2-48-73-60
60	112-60-6-73-99-55-16-114-78-3-71-96-100-12-68-56-84-87-24-5-29-122-52-38-30

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	R. O. Arbex and C. B. da Cunha , Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm, Transportation Research Part B: Methodological, 81 (2015) , 355-376. doi: 10.1016/j.trb.2015.06.014.
	M. H. Baaj and H. S. Mahmassani , An AI-based approach for transit route system planning and design, Journal of Advanced Transportation, 25 (1991) , 187-209. doi: 10.1002/atr.5670250205.
	M. H. Baaj and H. S. Mahmassani , Hybrid route generation heuristic algorithm for the design of transit networks, Transportation Research Part C: Emerging Technologies, 3 (1995) , 31-50. doi: 10.1016/0968-090X(94)00011-S.
	M. Bagherian , S. Massah and S. Kermanshahi , A swarm based method for solving transit network design problem, Proceedings of the 36th Australasian Transport Research Forum, (2013) , 2-4.
	D. Beasley , D.R. Bull and R.R. Martin , An overview of genetic algorithms: part 2, research topics, University Computing, 15 (1993) , 170-181.
	M. Bielli , M. Caramia and P. Carotenuto , Genetic algorithms in bus network optimization, Transportation Research Part C: Emerging Technologies, 10 (2002) , 19-34. doi: 10.1016/S0968-090X(00)00048-6.
	A. T. Buba and L. S. Lee , Differential evolution for urban transit routing problem, Journal of Computer and Communications, 4 (2016) , 11-25. doi: 10.4236/jcc.2016.414002.
	A. Ceder and N. H. M. Wilson , Bus network design, Transportation Research Part B: Methodological, 20 (1986) , 331-344. doi: 10.1016/0191-2615(86)90047-0.
	P. Chakroborty , Genetic algorithms for optimal urban transit network design, Computer-Aided Civil and Infrastructure Engineering, 18 (2003) , 184-200. doi: 10.1111/1467-8667.00309.
	P. Chakroborty and T. Wivedi , Optimal route network design for transit systems using genetic algorithms, Engineering Optimization, 34 (2002) , 83-100. doi: 10.1080/03052150210909.
	J. S. C. Chew, L. S. Lee and H. V. Seow, Genetic algorithm for biobjective urban transit routing problem, Journal of Applied Mathematics, 2013 (2013), Article ID 698645, 15 pages.
	S. Chien , Z. Yang and E. Hou , Genetic algorithm approach for transit route planning and design, Journal of Transportation Engineering, 127 (2001) , 200-207. doi: 10.1061/(ASCE)0733-947X(2001)127:3(200).
	L. Fan, Metaheuristic Methods for the Urban Transit Routing Problem, Ph. D thesis, Cardiff University (United Kingdom), 2009.
	L. Fan and C. L. Mumford , A metaheuristic approach to the urban transit routing problem, Journal of Heuristics, 16 (2010) , 353-372. doi: 10.1007/s10732-008-9089-8.
	L. Fan , C. L. Mumford and D. Evans , A simple multi-objective optimization algorithm for the urban transit routing problem, IEEE Congress on Evolutionary Computation, (2009) , 1-7. doi: 10.1109/CEC.2009.4982923.
	W. Fan and R. B. Machemehl , Optimal transit route network design problem with variable transit demand: genetic algorithm approach, Journal of Transportation Engineering, 132 (2006) , 40-51. doi: 10.1061/(ASCE)0733-947X(2006)132:1(40).
	W. Fan and R. B. Machemehl , Tabu search strategies for the public transportation network optimizations with variable transit demand, Computer-Aided Civil and Infrastructure Engineering, 23 (2008) , 502-520. doi: 10.1111/j.1467-8667.2008.00556.x.
	J. Guan , H. Yang and S. Wirasinghe , Simultaneous optimization of transit line configuration and passenger line assignment, Transportation Research Part B: Methodological, 40 (2006) , 885-902. doi: 10.1016/j.trb.2005.12.003.
	A. Jaszkiewicz , On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study, European Journal of Operational Research, 158 (2004) , 418-433. doi: 10.1016/j.ejor.2003.06.015.
	M. P. John, C. L. Mumford and R. Lewis, An improved multi-objective algorithm for the urban transit routing problem, in Evolutionary Computation in Combinatorial Optimisation, EVOCOP Lecture Series in Computer Science (eds. C. Blum and G. Ochoa), Springer, 2014. doi: 10.1007/978-3-662-44320-0_5.
	P. N. Kechagiopoulos and G. N. Beligiannis , Solving the urban transit routing problem using a particle swarm optimization based algorithm, Applied Soft Computing, 21 (2014) , 654-676. doi: 10.1016/j.asoc.2014.04.005.
	F. Kiliç and M. Gök , A demand based route generation algorithm for public transit network design, Computers & Operations Research, 51 (2014) , 21-29. doi: 10.1016/j.cor.2014.05.001.
	H. N. Koutsopoulos and N. H. M. Wilson, Determination of headways as a function of time varying characteristics on a transit network, in Computer Scheduling of Public Transport 2, (1985), 391–414.
	T. I. Magnanti and R. T. Wong , Network design and transportation planning: models and algorithms, Transportation Science, 18 (1984) , 1-55. doi: 10.1287/trsc.18.1.1.
	C. E. Mandl , Evaluation and optimization of urban public transportation networks, European Journal of Operational Research, 5 (1980) , 396-404. doi: 10.1016/0377-2217(80)90126-5.
	E. Mazloumi , M. Mesbah , A. Ceder , S. Moridpour and G. Currie , Efficient transit schedule design of timing points: a comparison of ant colony and genetic algorithms, Transportation Research Part B: Methodological, 46 (2012) , 217-234. doi: 10.1016/j.trb.2011.09.010.
	C. L. Mumford , New heuristic and evolutionary operators for the multi-objective urban transit routing problem, IEEE Congress on Evolutionary Computation, (2013) , 939-946. doi: 10.1109/CEC.2013.6557668.
	A. T. Murray , A coverage model for improving public transit system accessibility and expanding access, Annals of Operations Research, 123 (2003) , 143-156. doi: 10.1023/A:1026123329433.
	M. A. Nayeem , M. K. Rahman and M.S. Rahman , Transit network design by genetic algorithm with elitism, Transportation Research Part C: Emerging Technologies, 46 (2014) , 30-45. doi: 10.1016/j.trc.2014.05.002.
	G. Newell , Some issues relating to the optimal design of bus routes, Transportation Science, 13 (1979) , 20-35. doi: 10.1287/trsc.13.1.20.
	S. Ngamchai and D. J. Lovell , Optimal time transfer in bus transit route network design using a genetic algorithm, Journal of Transportation Engineering, 129 (2003) , 510-521. doi: 10.1061/(ASCE)0733-947X(2003)129:5(510).
	M. Nikolić and D. Teodorović , Transit network design by bee colony optimization, Expert Systems with Applications, 40 (2013) , 5945-5955.
	J. Pacheco , A. Alvarez , S. Casado and J. L. González-Velarde , A tabu search approach to an urban transport problem in northern Spain, Computers & Operations Research, 36 (2009) , 967-979. doi: 10.1016/j.cor.2007.12.002.
	S. Pattnaik , S. Mohan and V. Tom , Urban bus transit route network design using genetic algorithm, Journal of Transportation Engineering, 124 (1998) , 368-375. doi: 10.1061/(ASCE)0733-947X(1998)124:4(368).
	S. Schéele , A supply model for public transit services, Transportation Research Part B: Methodological, 14 (1980) , 133-146.
	R. Storn and K. Price, Differrential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report, International Computer Science Institute Berkeley, CA, 1995.
	Q. K. Wan and H. K. Lo , A mixed integer formulation for multiple-route transit network design, Journal of Mathematical Modelling and Algorithms, 2 (2003) , 299-308. doi: 10.1023/B:JMMA.0000020425.99217.cd.
	F. Zhao and A. Gan, Optimization of transit network to minimize transfer, Final Report BD015-02 Research Office Florida Department of Transportation, 2003.