物流配送车辆运行径路优化问题的仿真实现

摘要：利用旅行商问题的C-W节约算法，对物流配送的车辆运行径路进行仿真计算，通过实例计算，可以得出最优的解。这在高油价下对降低车辆及物流成本，有现实意义。

Abstract: Using TSP C-W saving algorithm, a simulation is carried out on logistic delivery vehicle routing problem. An optional solution is obtained through example calculation, which has realistic meaning on high oil period to reduce vehicle and logistic costs.

关键词：物流配送；运行径路；C-W节约算法；优化；仿真

Key words: logistic distribution；routing；C-W saving algorithm；optimization；simulation

中图分类号：F259.22 文献标识码：A文章编号：1006-4311（2010）32-0020-02

0引言

在物流配送中常遇到这样的问题：有一个中心货场，需向多个货主配送货物，车辆在货场装载货物后发出，完成任务后返回货场，如何确定车辆行驶线路，使车辆走行路径最短。在货物量较少的情况下，车辆不能满载，用一辆车完成一项任务，对车辆造成浪费，往往安排一辆车完成多个任务，完成多个货主的配送任务，提高车辆的利用率。这个问题的解决对加速货物周转、提高车辆的利用率，降低运输成本，有非常重要的意义。本文对该问题进行了深入分析，提出了计算办法，并通过计算机编程实现了最优路径的计算办法。

1算法

车辆配送问题，是典型的旅行商问题，旅行商问题（Traveling Salesman Problem简称为TSP问题）是一个NP难题，还没有有效的通用算法。但是旅行商问题的解决方法，对解决诸如超市货物配送问题、垃圾车的走行线路问题，民航机组人员的轮班安排问题等等，都有积极借鉴作用，所以，TSP问题的求解及应用具有现实意义。本文利用旅行商问题的C-W节约算法对非满载的车辆走行径路的优化进行计算机仿真求解。

1.1 算法原理如图1所示，由货运站P向两个客户A，B送货，P至A，B的最短距离分别为l1和l2，A，B间的最短距离为l3，客户A，B的货物需求量分别为q1和q2。

对上述问题，最简单的取送方法是用两台车辆分别对A，B两个客户运送所需货物，然后各自返回货运站。使用该种配送方案时，配送车辆的走行总里程为：

如果改为由一辆车辆向A，B两个客户巡回送货（设q1+q2＜配送车辆的载重量），则配送车辆的走行总里程为：

l=l1+l2+l3

后一种配送方案比前一种配送方案节约的车辆走行里程为：

ΔI=[2（l1+l2）]-（l1+l2+l3）=l1+l2-l3

ΔI为节约量公式，从图形看，它等于三角形的两个邻边之和减去对边的差。如果货场用点o表示，A，B两个客户用点i和j表示，则s（i，j）=Cj0+C0i-Cji，其中，C0i为源点o到点i的路段长度，Cj0为点j到源点o的路段长度。对于不同的点（i，j），S（i，j）越大，车辆通过弧（i，j）所节约的路程越多，因而应优先将其插入到旅行线路中。

1.2 算法步骤

1.2.1 将源点O与其他各点相连，并计算节约值s（i，j）=Cio+c0j-Cij，将计算结果填入节约值表；

1.2.2 考察节约值表格中最大元素S（i，j）对应的点i和点j，检查是否满足下列条件：

①点i和点j均不在己构成的线路上，则可连接点i和点j，得到线路段0→i→j→0，转步骤（3）；

②若点i或点j在已构成的线路上，但不是线路的内点（即不与源点0直接相连）， 则可以连接，连接后得到线路段0…→i→j→0或0→i→j→…0，转步骤（3）；

③若点i和点j位于己构成的不同线路上，且均不是内点，则后得到线路段0→…→j→j→…→0，转步骤（3）；

④若点i和点j位于已构成的同一条线路上，则不能再进行连接，转步骤（3）。

1.2.3 划去第i行和第j列，即i点不能再到其他点，而j点也不能由其他点到达；

1.2.4 若所有元素均被划去，则己得到完整线路，算法终止;否则，在没被划去的元素中选择最大元素，转步骤二。

本方法通过以上各个步骤，使得解逐步得以改进，最后达到满意解。算法方框图见图2。

2物流配送车辆运行径路仿真实现

某铁路车站货场（编号为0），有5个货主的货物需要配送（编号为1，2，3，4，5）。由于货物的重量和体积的关系，车站用一辆车完成任务。已知货场到各个作业地点的走行距离（如表1）。要求确定一条最短的走行路线，使得总走行距离最短。

利用C语言编程，对程序运行。通过程序运行首先得出节省表如表2。

在节省表中Max=2，Min=3为最大节省，则计算机自动划去第二行和第三列个数值，得出新一轮的节省表（表3），同时输出链路图：0—2—3—0。

如此方法，在极短时间，计算机算出最终的链路图为：

0—1—2—3—4—5—0，这就是最终得出的车辆走行最短线路。此时，车辆走行距离为：18+22+19+12+13+25=109km。

3结论

从算例可以看出，C-W节约算法在中心货场车辆非满载的情况下，利用计算机可以得出最优解，效果理想。这种仿真算法可以推广到超市货物配送、垃圾车走行线路的选择、民航机组人员的轮班安排等问题的解决方面。

在利用计算机建设车辆配送线路优化智能指挥系统时，还要考虑城市交通情况，天气情况等因素，做出全面考虑。

参考文献：

[1]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2001.6.

[2]运筹学教材编写组.运筹学[M].北京:清华大学出版社，1997.

[3]郭耀煌等.运筹学原理与方法[M].成都:西南交通大学出版社，2000.11.

[4]马良.旅行推销员问题的算法综合[J].数学的实践与认识.2000，30（2）：157～165 .