Multi-objective optimisation of a commercial vehicle complex network

Abstract

In this project we build on research that has been done by Joubert and Axhausen (2013), who built a commercial vehicle complex network for Gauteng. Two shortcomings are identi ed in the approach they followed. The rst shortcoming is the approximations used to determine whether an activity formed part of a cluster. These approximations resulted in some activities to be assigned to the wrong clusters, and other activities to not be assigned to any cluster. The second shortcoming is that the completeness of the complex network was never explicitly considered when they evaluated the di erent combinations of input clustering parameters. We address the rst shortcoming by generating a concave hull for each cluster. The concave hull envelopes all points in the cluster, and one can accurately determine whether an activity forms part of a cluster. To generate the concave hulls, we integrate the Duckham Algorithm with the existing clustering algorithm used by Joubert and Axhausen (2013). The rst step of the Duckham Algorithm is to generate the Delaunay triangulation of the cluster. For some combinations of input clustering parameters, more than 2% of the clusters were degenerate. A degenerate Delaunay triangulation occurs when three or more points in a cluster are colinear (lie on a straight line), or when four points in a cluster are cocircular (lie on the circumference of a circle). No valid Delaunay triangulations can be generated for these clusters. We suggest to deal with these degeneracies by using the weighted average of the points as a reference to the cluster, instead of simply ignoring it. We consider the completeness of the complex network as part of a multi-objective problem: we cannot maximise completeness without making a trade-o with computational complexity. We address this multi-objective problem by conducting a multiple response surface experiment and performing multi-objective evaluation by constructing two e cient frontiers. From the multiple response surface experiment, we found that the input clustering parameters ( , pmin) that optimises the completeness of the complex network, while minimising the computational complexity, is (1, 2). From the multi-objective evaluation, we determined that in general, using = 1 will result in an e cient point. To conclude, we use input clustering parameters (1, 2) to build a commercial vehicle complex network in the Nelson Mandela Bay Municipality, and perform various network analyses on this network.