多点物流配送车辆路径问题（VRP）优化与实证分析.docVIP

多点物流配送车辆路径问题（VRP）优化与实证分析 　　摘要：本文应用扫描算法对多点物流配送车辆路径问题进行优化，借助计算机编程实现多目标、动态车辆调度和线路优化。以河北快运为例进行实证分析，结合实例进行测试和结果分析，证明其可行性，使该算法设计更好地适应实际的需要。 　　关键词：多点物流配送；车辆路径问题；优化 　　基金项目：广东省高等教育教学研究和改革项目：物流专业产教融合协同育人平台建设研究 　　在配送线路优化设计中，通常有两类问题：一类是寻求两点之间最短路径，此类问题一般采用图论中求解最短路问题最好的算法Dijkatra算法进行优化。另一类是寻求从某一点到其余各点的最短路径，即物流配送网络中有一个配送中心和n个节点，车辆由配送中心出发，服务完n个节点再返回配送中心。这类问题就是多点物流配送车辆路径问题。该问题的研究目标就是对一系列客户需求点设计适当的配送线路，并在满足一定约束条件（如供应量、需求量、车载限制、时间限制等）的基础上，实现优化目标（如里程最短、费用最省、时间最少等）。本文笔者重点讨论由一个配送中心向多个客户进行共同配送的车辆路径问题。 　　1.模型的建立 　　多点物流配送车辆路径问题（Vehicle Routing Problem ，VRP）最早是由Dantzig和Ramser于1959年首次提出的，后被证明属于NP难题行列。 　　一般车辆路径问题描述为：某配送中心有[M]辆车，需对[N]个节点（客户）进行运输配送，每个节点的需求量为[gi]（[i=1，2，...，N]），每辆配送车辆的最大载重量为[q]。设[cij]表示节点[i]到节点[j]的运输成本，如时间、费用等。为构建数学模型的方便，将配送起点编号为0，各个配送任务节点标号为1，2，… N，配送中心以及货运节点统一用点i（i=0，1，2，…N）来表示。变量定义如下： 　　[yki=1 节点i的任务由车辆k完成0 否则xijk=1 车辆k从节点i行驶至节点j0 否则] 　　建立VRP数学模型： 　　[minz=ijkcijxijkigiyki≤q ?k式（1）kyki=1M i=1，2，…，Ni=0式（2）ixijk=ykj j=1，…，N；?k式（3）jxijk=yki i=0，1，…，N；?k式（4）] 　　其中，式（1）为车载容量约束；式（2）保证每个节点的运输任务仅由1辆成完成，且所有任务则由M辆车协同完成；式（3）和式（4）限制到达和离开某一客户的车辆仅有1辆。 　　2 .模型的求解思路 （用VRP 扫描法） 　　2.1 VRP 扫描算法基本思想 　　扫描法（Sweep Algorithm） 目的在于求解车辆调度问题，并针对几个求解相似问题的算法进行比较，证明该算法所求得的解较优于其他的方法，此方法属于先分群再排路线的方法，此方法分为两阶段： 　　第一阶段：用坐标表示各需求点的区位，然后任取一需求点为起点，以车辆容量为分群的约束，再以该需求点为零度按顺时针或逆时针的方向，进行顾客的扫描分群； 　　第二阶段：依据求解旅行商问题（TSP）的算法，求解各顾客群的排程。 　　2.2 VRP扫描算法求解步骤 　　2.2.1确定配送中心和各个节点的位置和需求量； 　　2.2.2以配送中心为原点，确定一尚未使用车辆，从最小角度且尚未指派的节点开始，沿着顺时针或逆时针方向扫描，当该车辆容量超限时，结束该条线路； 　　2.2.3重复上述步骤，生成新的线路，直至所有节点都被排入线路； 　　2.2.4依据TSP算法，求解出各站点在各线路上排定的顺序，使行驶路线最短，成本最低。 　　3.算例分析 　　3.1问题描述 　　本文以“邯运杯”全国大学生物流设计大赛案例中的河北快运公司为例进行分析研究，本文中的数据都来源于大赛案例。河北快运下设四个子公司分别为天恒、天昊、天诚以及天信。河北快运的总分拨点设在廊坊。河北快运2006年及2007年业务量如图1和图2所示。 　　由图1和图2知，河北快运下设的四个货运子公司每年货运量差距大，每月总货运周转波动幅度大，且各子公司之间存在着相互竞争的局势，不利于创造双赢。从中总结得出河北快运需在车辆调度和配送线路选择方面进行综合优化。 　　3.2问题求解 　　为了研究的需要，对模型进行一些假设：①河北快运子公司间的竞争可协调，实现资源的统一调配；②假设所有车辆具有相同容量，车载限额40吨；③暂不考虑货物的缺失成本。④利用计算机进行求解，详细计算过程略，直接得出优化结果。 　　具体步骤： 　　①利用VB编程，创建运输配套程序窗口（与总公司的SQL数据库相连），结合算法构建一个比较完善的运输调度系统。 　　②通过运输配套程序窗口，获取多目标配送相关的信息，其中包括货物种类、