一种部分约束满足车辆路线问题及其求解算法

A Partial Constraint Satisfaction Vehicle RoutingProblem and Its Solving Algorithm

描述了一类过度约束车辆路线问题,其中可用车辆数较少而时间窗口等其它约束又不允许放松,因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理,相应的优化目标是最小化未访问顾客的损失和。本文给出了求解这类特殊问题的一种禁忌搜索算法设计,并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。

A kind of over-constrained vehicle routing problem is described, in which there has not been any feasible solution because the available vehicles are too limited and the time-windows or other constraints can not be relaxed. In such a situation, the problem can be transformed to a partial constraint satisfaction problem to be resolved. Accordingly the optimization objective will be modified as minimizing the sum of the costs for not visiting some customers. We provide a tabu search algorithm for solving this special kind of problem, and further compare it with some other commonly used methods through several examples. Finally, we analyze the practical significance of our model and method.