A layered network formulation for the safe walking route design problem

摘要

This paper proposes a mathematical optimization model for designing safe walking routes for children from school to homes. We focus on the existing bi-objective model, the safe walking route design problem, which minimizes both the total walking risk and the total route distances for all children from school to home. The original problem assumes that the combined routes for all children forms a directed out-tree rooted at the school. However, making this assumption excludes solutions such as those involving cycles. This paper explores how to relax the assumption that the graph is an out-tree by using a layered network constructed from the original network. Using the layered network formulation, we obtain some solutions that have better objective values than those obtained by the original formulation when we strongly emphasize reducing the risk objective. The results also show that the new formulation produces the same out-tree solution when minimization of the risk objective and the distance objective are suitably balanced.