基于改进节约法的配送路线优化问题研究

基于改进节约法的配送路线优化问题研究

doi：10.3969'j.issn.1005-152X.2010.h23.0311引言在采用节约法求解配送车辆的线路优化问题(VehicleRoutingProblem，简称VRP)时，通常要满足以下基本约束：(1)收货人对货物的要求；(2)收货人对货物送达时间的要求；(3)收货人对地点的要求；(4)路线允许通行的时间限制；(5)运输工具载重能力的限制；(6)积载能力的限制；(7)配送中心的能力；(8)自然因素的限制。然而，在实际配送中，城市道路日益显现出负担的繁重，交通阻塞问题已是社会常见的问题之一，要想及时准确、高效率地完成配送任务，必须对配送线路的路况进行充分的考虑，如果没有充分考虑路况，在配送时就不能保证及时、高效地完成任务，客户的服务水平就得不到保证。在以往的配送问题研究中[1-3]，常假设不存在道路受阻的情况，而未将交通的通畅度考虑在内，因此，得到的实际配送时间和计划配送时间并不吻合，甚至相差很大。例如：配送车辆在市中心行驶一百米，实际上要比在郊区线路上走一百米用的时间长，但在用节约法选择配送路线时，仅考虑了路程的长度。要解决这一问题，就需要对不同的配送路线进行一个有效距离的转化，使得所优化的“配送线路”更接近于现实中的配送线路，这样更能及时、准确、高效地完成客户的任务。因此，本文提出了改进节约法求解配送线路优化问题，在该问题中，除了考虑上述基本约束条件，还考虑了“易忽略的其它重要影响因素”，包括：(1)不同地方的道路状况：(2)交通阻塞的时间；(3)等交通指示灯的时间；(4)道路的最高限速情况。本文通过一定的转化，将这些“易忽略的其它重要影响因素”转化成有效距离来看待，通过“转化系数”来确定实际的有效距离，这样可将问题的求解难度降低。2典型节约法的原理3改进节约法的思路节约法虽然考虑了路程的最大节约，但它没有把道路的不同状况考虑在内，针对这一问题，本文提出了改进的节约法。改进的节约法的基本思路为：首先，计算出配送中心到各个被配送点的有效距离及各个被配送点之间的距离。其次，计算各被配送点之间相互间的“有效节约里程”的大小和各被配送点的收货数量或重量。最后，在车辆如载重允许的条件下，将各个可能入选的送货点衔接起来，形成一条配送线路，如果卡车不能满足全部送货要求，可先安排一辆，然后按照上述程序继续安排第二辆、第三辆或更多，直到全部被配送点连在多条配送线路上为止。具体操作步骤为：(1)对配送的公路进行划分。例如：划为“市区线路”、“城郊线路”、“乡镇线路”(还可划分的更细，如将“市区线路”按拥挤程度再划)，并进行有效距离的转化。假设“城郊线路”时速Xkm/h；“市区线路”时速Ykm/h；“乡镇线路”时速Zkm/h，根据实际情况并参照公路等级车速规定，取得对应等级线路车速，来计算其“转化系数”。(2)计算有效最短距离。根据配送网络中的已知条件，计算配送中心到各个被配送点之间的最短距离。将实际距离转化为有效距离的步骤如下：STEP1对“城郊线路”、“市区线路”和“乡镇线路”进行转化。STEP2利用系统工程学的知识，求出相对应的权重，分别取各自权重的倒数，作为对应的转化系数。STEP3利用实际距离和转化系数之积来确定有效距离。(4)将节约里程进行分类，按照从大到小的顺序排列。(5)确定配送线路，并根据车辆载重或运量平衡进行不断地修正，最终形成可行的配送线路。4转化系数的确定4.1划分配送线路等级一级公路：是连接重要政治经济文化中心、部分立交的公路，设计车速(km/h)：60-80。二级公路：是连接政治、经济中心或大工矿区的干线公路、或运输繁忙的城郊公路，设计车速(km/h)：40-60。三级公路：是沟通县或县以上城市的支线公路，设计车速(km/h)：30-40。四级公路：是沟通县或镇、乡的支线公路，设计车速(km/h)：30。4.2确定相应线路的转化系数根据权重的求解原理[4]和步骤来确定对应等级公路的转化系数。“市区线路”、“城郊线路”、“乡镇线路”分别用“S”、“C”、“X”来表示。根据前面所提到的公路等级和实际的交通拥挤程度，假设“市区线路”车速30km/h，“城郊线路”车速70km/h，“乡镇线路”车速40km/h。根据上节提供的方法，计算出各个线路的转化系数。(6)确定配送线路，如图3。(2)决定修正方案时，若出现节约里程相等的情况，此时应考虑车辆相关系数，如额定载重或线路运量均衡的问题，选择几方面都能兼顾的线路入选，或重新再形成一条新的配送路线。6结论