A Proposal and Evaluation of Heuristic Scheme to Determine Regular Route of Community Buses with Minimum Average Travel Time

摘要

This paper studies a problem of determining regular route of community buses in such a way that the degree of satisfaction of the passengers will be maximized. The satisfaction of passengers is assumed to be dependent on the travel time to their destination and the degree of congestion in the bus. In what follows, we call this problem regular bus routing problem (BRP, for short). We propose a heuristic scheme for solving BRP based on GRASP. In executing GRASP, that is known as a typical metaheuristic based on the multi-point search technique, several initial solutions are randomly generated, and are locally improved by using neighborhood search procedure. In the proposed scheme, we improve the procedure for generating initial solutions in such a way that it generates a large number of feasible (and possibly better) solutions as the initial solutions with a sufficiently short computation time. The effect of the proposed scheme is evaluated by comparing it with a scheme in which initial solutions are generated fully randomly. The result of experiments implies that the proposed scheme can output better solutions, although the number of initial solutions per time is less than 1% of the fully randomized scheme.