摘要：研究了一类新的车辆路线问题（VRP）——整合逆向物流的多车辆路线问题（MVRPRL）。该问题的特点是客户可以同时取货和发货，而且客户发货量是在路线安排前是不确定的。首先用三角模糊数表示客户发货量，建立了基于模糊置信度理论的多目标模型；然后设计了基于模拟的改进禁忌算法来求解该模型:用模拟的方法计算路线失败值，在路线搜索中采用路线内部改善和路线间改善两类邻域操作，而且采用了重起策略。最后计算结果表明该方法优于传统的扫描算法，整合逆向物流的运输费用比正逆向分别运输之和减少了43%。
关键词：逆向物流；集散一体化；置信度理论；禁忌搜索；模糊模拟
1 引言
随着环境污染的日益严重，一些国家（如德国、日本和美国）已经立法要求企业回收产品的包装材料[1]，我国也制定了电子产品回收的相关法规[2]，因此逆向物流备受关注。为了减少运输费用，如何将逆向物流整合到正向物流中，成为物流企业十分关注的问题。
该问题与一般车辆路线问题（VRP）相比，具有以下特点：（1）客户需要配送（或者发送）一定量的货物，或者既发送货物也接受货物；（2）客户的发货量（逆向需求）是不确定的，本文假设其为三角模糊变量；（3）计算难度增加。由于VRP问题是NP-Hard难题，整合逆向物流的车辆路线问题包含VRP且逆向需求为不确定值，所以其计算难度增大。
针对该问题的特点，以车辆数和运输费用为目标，建立了基于置信性理论的模糊规划模型。在不确定条件下车辆路线问题，一般路线解在一定的置信度水平下取得。但由于在实际过程中规划的路线可能出现失败，将产生处理失败路线的额外费用。决策者更希望找到使计划费用和失败费用之和最小的路线安排，所以本文将失败费用包含到目标函数中。
针对该问题的计算复杂性，提出用基于模拟的禁忌搜索算法来求解。采用包括线路内部交换和线路间交换的邻域搜索和重起策略来开发邻域结构，然后用基于模拟的方法求解目标函数。
2 文献综述
将不确定条件下的逆向需求整合到正向路线中的研究几乎没有。已有的研究主要集中在确定条件下的集散货物路线和单向不确定条件下的车辆路线问题的研究。如文献[5]首先介绍了同时集散货物路线问题，提出了先聚类后路线安排的算法；文献[6]从逆向物流的观点研究了同时集散货物路线问题，设计了基于插入算法的启发式算法；文献[7]提出基于不可行解的启发式算法；文献[8]提出了基于记录更新和禁忌表的启发式算法。这些研究虽然整合了逆向需求，但均假设其为确定值。
不确定条件下的单向车辆路线研究包括随机车辆路线问题和模糊车辆路线问题：文献[9]首先用模糊变量处理了车辆路线中的不确定参数，用扫描算法求解了该问题；文献[10]用基于可信性理论建立带时间窗的车辆路线问题，并提出混合遗传算法求解该问题；文献[11]和文献[12]研究了随机车辆路线问题。文献[9-12]虽然考虑逆向需求的不确定性，但逆向需求没有整合到正向车辆路线中。
另外，文献[1]研究了随机环境下的单车辆集散货物路线问题，但是在一些新系统中，由于缺乏历史数据，参数难以表示为随机变量，而且实际中多车辆也是经常遇到的。