Abstract: The travel time of vehicles is always stochastic. In view of this, a stochastic programming model including time-window and vehicle capacity constraints is given to minimize the number of vehicles, traveling distance, the dissatisfaction of costumers, and the time variance of different routes at the same time. A heuristic algorithm based on tabu search is raised to solve the model, and several cases are generated to prove the efficiency of the algorithm. And the computation result shows that the time-variance of different routes can be optimized without increasing the cost or decreasing the service quality of costumers.

Key words: operations research, time-windows, stochastic programming, tabu-search, uncertain travel-time, load balancing, VRP

摘要： 本文针对车辆调度实际运行过程中时间的不确定性问题,提出了包含时间窗口、车辆容量约束的配送服务线路随机规划模型,以最小化调用的车辆数目和运行距离,降低顾客的不满意度并且尽可能保证每条路线的均衡性。结合模型,给出了基于禁忌搜索的混合启发式算法,并且生成多个算例,依据算例结果说明模型和算法优越性,同时说明可以在不降低顾客满意度和不提高总运输成本的基础上,降低各条线路之间的时间差异。

关键词: 运筹学, 时间窗口, 随机规划, 路线时间方差, 禁忌搜索, 不确定时间, 车辆路线