Application of Simulated Annealing to Routing Problems in City Logistics

Abstract

The R & D activities to realize systems which provide road traffic information and route guidance have been conducted as core systems of Intelligent Transport Systems (ITS). However, the implementation of these systems will have less effect on freight transport unless logistics operation is rationalized in parallel to the development of ITS. On the other hand, according to the expansion of internet, information has been exchanged with extremely high speed and low cost. Nevertheless, goods must be moved in the real space. Ecommerce has caused the increase of door-to-door deliveries. The demands for high-quality delivery services such as small-amount high frequency deliveries with time windows have been made by many clients (including companies and individuals). The loading rate of trucks has decreased and the rate of freight transportation in total road traffic has increased. The rationalization in terms of increasing the loading rate and decreasing the total travel time is aimed not only for reducing operational costs in each freight carrier but also for relieving traffic congestion, saving energy and reducing the amount of CO2. Freight transportation in urban areas that is described above is called city logistics (Taniguchi et al. 2001). Many researches on routing problems have been appeared in the literature. Comprehensive and detailed explanations of theoretical models and solutions of them are given by Toth & Vigo (Toth & Vigo, 2002). On the other hand, in the context of city logistics, real routing problems should not be based under the assumption on the symmetry of the link costs of visiting customer j after customer i or customer i after customer j, pij=pji, and other related mathematical properties, as triangular property etc. This is due to the fact that in an urban environment routes using the streets have to account for one way streets, issues related to regulations at intersections. In addition, travel time might vary according to traffic conditions, that is to say, it might be time dependent. Moreover, in urban road networks, demands might be located on not only spots on streets but also streets themselves. This chapter is aimed for describing the original solution, which has been invented by the authors of this chapter, to routing problems in city logistics. At the beginning of this chapter, a variety of routing problems will be introduced and followed by the explanation of features of routing problems in city logistics. And then, a practical solution method, which is composed of a data model, transformation rules of a solution on the data model and an overall algorithm using Simulated Annealing for solving O pe n A cc es s D at ab as e w w w .ite ch on lin e. co m