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.

Zones in Macro Transport Model described with "optimal" points, part III: Second Optimal Gravity Center

This is third part of Spatial Analysis of Zones for macroscopic transport modeling. Now I focus on problem of location of "second optimal point", being transfer point for journey within zone (in this case it’s county).

Two other parts of this series can be found here, and here where You can find description of input database. The previous parts focus on: 1) Where is optimal transfer point for journeys within area 2) where is optimal transfer point for journeys from region to center of network (i.e. from region to state capital, i.e. from Kent to London, from Bretagne to Paris, from Liguria to Rome, from Silesia to Warsaw).

Problem: 

Now I assume that one point location is fixed, and it’s legal capital of area (county seat). With this constrain I search for second point that will minimize travel times within area.

 Method: 

second gravity point can be defined as follows: 

Where:

SCG          is second gravity point

P                is population

p                is zone index

i                 is index for addresses within area

d                is distance

C               center of area

Results:

Minimization problem wasn’t monotonic, and had some local minima, thus it was solved by greedy algorithm (enumeration), global optimization approach like here was not employed due to small complexity.

Following diagram show goal function values in 3d plot:

Summary:

Second Optimal Point for area can be a good hint to describe area. It may be a hint when You try to place connector, or describe travel times within Zone. It may be also a good hint when defining location of Zone Centroid.

Zones in Macro Transport Model described with "optimal" points, part II: Optimal Access Point

This post reports on results of my spatial analysis of transport zones.

I define optimal location of access point for area. Location guarantees minimal overall transport costs for journeys from area to central point of region (i.e. Capital)

I define Optimal Access Point, being point that provides minimal sum of travel times for journeys to central point of network (i.e. Capital).

Presumptions for this analysis (transport network, demand model) were described here. additionally what You can find there is analogical definition of point that minimizes travel times within area (Center of Gravity)

Method:

This analysis was done for Counties (around 50k inhabitants , 2k sq. km ). 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²)

For each zone I find an “Optimal Access Point”, being defined as follows:

Where:

P                is population

d                is distance

M               is metropolital point (central point of network)

A, B           are parameters crucial for results, namely:

if (B/A -> Inf ) -> point = center of network ,

if ( B/A -> 0) -> point ~ center of gravity for area

Solution: 

Goal function was strictly monotonic, and continuous, so optimization was straightforward, with following results

Boundary = area boundary

X = central point for area

triangle = gravity center for area

O = Optimal Location Point

Background color = goal function value

the A, and B parameters will place Optimal Access Point on line between Center of Gravity for region, and Central point of network, and line can be a curve rather than straight line

Conclusion 

Optimal Access Point location can be a good hint during decision of transit network design, i.e. one can locate multimodal stop at point that minimizes both Access Time to Central point of Network, and is close to Center of Gravity.

PS. Cartesian distance was proposed here (for simplicity), however any other distance measures can be employed, i.e. travel distance.