Transit Network Design Problem for “monocentric” network solved by means of poli-criterial genetic optimization method.

Summary:

Paper shows an approach to solve Transit Network Design Problem. Considered problem covers regional transport system (Lublin region in Poland). Input data were GIS transport network and population distribution. Complex optimization problem was simplified by means of graph theory methods. Final optimization problem was poli-criterial genetic algorithm. Result of solving problem was Pareto frontier, being a set of non-dominated solutions. Optimization process was continuation of Visum Zone definition described here.

Background: 

I got GIS database consisting of:

·        Location of  place with information about their population (fig.1)

·        Transport network (roads + railway) (fig.2)

·        Administrative division (zones) (fig.1+2) (each zone was about 50k inhabitants, 2k km²)

I presented the network as a graph consisting of 82 edges: 

fig.3

Method:

I solved poli-criteria problem of Network Layout Optimization. Two contrary criteria were:

1)     Operator cost minimization criteria: Total network length (km) and

2)     Passenger Cost minimization criteria: Total passenger kilometers (paskm) represented via two separate criteria:

a.     Travel times to get co central points of the network

b.     Overall accessibility, being DistanceMatrix x OD Matrix ^(-1) (reciprocal was employed to transform criteria into minimization)

Decisive vector was 82 element Boolean vector. Each element of vector was reflecting graph edge.

I solved problem using Multi-objective Genetic Algorithm, minimizing three given criteria. Result was Pareto Frontier. Pareto frontier final population is shown here. Additional criteria being standard deviation of accessibility is proposed:

Nuber In Pareto final population (Lp)	Passenger cost 1	Operator Cost	Passenger Cost 2	Additional Criteria
	Passenger kms[1000 paskm]	Network Length [km]	Accessibility [pop./km]	Standard Deviation of Accessibility for Zones
8	161 000	1 218	732 902	99,3
22	161 000	1 282	733 704	99,3
10	161 000	1 276	733 447	99,3
28	128 000	1 423	723 114	66,2
2	122 000	1 851	640 084	62,8
20	123 000	2 241	653 834	63,7
15	122 000	2 457	667 836	62,8
1	133 000	1 624	814 889	71,1
23	132 000	1 707	823 710	67,5
19	126 000	2 400	882 689	68,2
27	121 000	2 700	900 210	59,6
17	121 000	3 521	921 467	59,6
21	136 000	2 445	886 533	72,6
18	122 000	2 556	900 101	62,8
7	122 000	2 898	908 254	62,8

 Pareto frontier for two criterias can be seen here:

Network diagrams for selected solutions are shown here:

network no 8

network no 17

network no 22

Conclusion:

User friendly tools combined with good quality of input data can perform much more than you expect with basic transport models. Built-in optimization for tranpsport modeling - sounds good.