一种求车流组织优化方案的启发式算法

A heuristic algorithm for solving vehicle scheduling problem

车流组织问题不仅是经营性运输公司和大型企业运输部门的一项日常性的基础工作,而且公共服务领域的许多问题也与此有关。由于此类组合优化问题是"NP-hard"的,并且在制定行车方案时需要考虑的变量很多,因此只能采用启发式方法求解。本文运用集分割模型,在车辆装载量既定的情况下,首先将问题简化为多TSP问题,再运用分枝定界法求出各TSP问题的巡回路线。

Vehicle scheduling is a common fundamental work not only for every professional transporting company and the transporting branch of each large enterprise, but many problems in public services. Because this combinational optimazition is ＂NP -hard＂ and many variables must be considered in making route and schedule, so heuristic approach can be adopted. In this paper, the burden for capacitated vehicle is given. First, the problem to multiple TSP by set partitioning model is simplified, and then each TSP by branch and bound algorithm is solved.