物流配送多环节的建模优化求解方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇物流配送多环节的建模优化求解方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：文章从物流配送的路线优化和车辆配装两个作业环节，提出了建模优化求解方法解决物流配送合理化问题，并应用于实例中，用实例证明了建模优化求解方法的合理性和可行性。

关键词：合理配送；多环节建模；优化

一、配送线路的优化

配送线路是各送货车辆向各个用户送货时所要经过的线路。配送线路优化的基本条件是所有客户的需求量总和不大于一辆车的额定载货量。配送路线的优化目标有多种，如效益最高、成本最低、路程最短、准确性最高、吨公里数最小等，目标的选择是根据配送的具体要求、配送中心的实力及客观条件来确定的。随着配送的复杂化，配送路线的优化一般要结合数学方法及计算机求解方法来制定合理的配送方案。下面主要介绍确定优化配送方案的一个较成熟的方法――节约法，也叫节约里程法，它以吨公里数最小为目标。

（一）节约法的基本思想

为方便介绍，假设：配送的是同一种或相类似的货物；各用户的位置及需求量已知；配送方有足够的运输能力；利用节约法制定出的配送方案除了使总的周转量最小外，还应满足：方案能满足所有用户的到货时间要求；不使车辆超载；每辆车每天的总运行时间及里程满足规定的要求。

利用里程节约法确定配送线路的主要出发点是，根据配送方的车辆运载能力及其到客户之间的距离和各客户之间的相对距离，来制定使配送车辆总的周转量达到或接近最小的配送方案。

设P0为配送中心，分别向用户Pi、Pj送货。P0到Pi和Pj的距离分别为d0i和d0j，两个用户Pi、Pj之间的距离为dij，送货方案只有两种，即配送中心P0向用户Pi、Pj分别送货和配送中心P0向用户Pi、Pj同时送货。比较两种配送方案：

方案a的配送线路为：P0PiP0P jP0，配送距离为：da=2d0i+2d0j；

方案b的配送线路为：P0PiPjP0，配送距离为：db=d0i+d0j+dij。

显然，da不等于db，用Sij表示里程节约量，即方案b比方案a节约的配送里程：Sij=d0i+d0j-dij。

根据节约法的基本思想，如果一个配送中心P0分别向n个客户Pj（j=1，2……，n）配送货物，在汽车载货能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多，里程节约量越大，配送线路越合理。

（二）实例

某一配送中心P0向10个客户Pj（j=1，2……10）配送货物，其如下图1所示。图中括号内的数字表示客户的需求量（t），线路上的数字表示两结点之间的距离。配送中心有2t和4t两种车辆若干可供使用，试制定最优的配送方案。

第一步：计算最短距离。根据配送网络中的已知条件，计算配送中心与客户、客户之间的最短距离，结果见表1。

第二步：根据Sij=d0i+d0j-dij，计算节约里程，结果见表2。

第三步：将节约里程Sij进行分类，按从大到小的顺序排列，得表3。

第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图：

初始方案：对每客户分别单独派车送货，结果：P0P1P0，P0P2P0，P0P3P0……P0P10P0，配送线路：10条；配送距离：148；配送车辆：2吨×10。

修正方案：按节约里程Sij由大到小的顺序，连接P1和P2，P1和P10，P2和P3，得线路A；在剩余的Sij中，最大的是S3，4和S4，5，此时P4和P5都有可能并入线路中，但考虑到车辆的载重量及线路均衡问题，连接P4和P5形成一个新的线路B；接下来最大的Sij是S1，9和S5，6，由于此时P1已属于线路A，若将P9并入线路A，车辆会超载，故只将P6点并入线路B，修正方案再继续按Sij由大到小排出S9，10、S1，3、S2，10、S2，4、S3，5，由于与其相对应的用户均已包含在已完成的线路里，故不予考虑。把S6，7对应P7点并到线路B中；其次是S7，8，考虑到配送距离的平衡和载货量的限制，不将P8点并入到线路B中，而是连接P8和P9，组成新的线路C，得到最终方案。

这样得到最终配送方案：

配送线路A：P0―P3―P2―P1―P10―P0使用一辆4t车

配送线路B：P0―P4―P5―P6―P7―P0使用一辆4t车

配送线路C：P0―P8―P9―P0使用一辆2t车

配送线路：3条

配送距离：80km

配送车辆：2t×1+4t×2

使用节约里程法的注意事项：适用于需要稳定的用户；应充分考虑交通和道路情况；充分考虑收货站的停留时间；当需求量大时，求解变得复杂，需要借助计算机辅助计划。

二、车辆合理配装

（一）合理配装问题的数学模型

配送车辆配装技术要解决的主要问题就是在充分保证货物质量和数量完好的前提下，尽可能提高车辆在容积和载货两方面的装载量，以提高车辆利用率，节省运力，降低配送费用。

在解决合理配装问题时，通常把其视为一个优化问题采用动态规划或者整数规划进行求解。合理配装问题的数学模型一般表述为：

MAXf（x）= PkXk

PkXk≤G

满足XK≥0

K=1，2，...n

式中，XK为第K种货物的数量；PK为第K种货物的价值系数；WK为第K种货物的重量；G为装货车辆的载重量。

（二）在合理配装基础上实现合理配送

对于合理配送问题可以把它理解为由多次合理配装问题所组成。即前一阶段合理配装问题优化解中的被装车的货物不再参与后一阶段合理配装问题中。后一阶段合理配装问题中的变量只是那些前一阶段剩余下来的、还未被装车的货物。这样，每求解一个合理配装问题，就可以解决一批货物的合理配送问题。如此反复进行，直到解决全部货物的合理配送问题。

（三）实例

货车载重量G=50，现有8种货物，其重量分别为W1=19，W2=13，W3=12，W4=7，W5=16，W6=8，W7=18，W8=19，如何配装才能充分利用货车的运载能力。

求解步骤：

确定该合理配装问题的数学模型：

设Xi=为第i件货物的件数，则该装货问题的数学模型为：

MAX f(X)=19X1+13X2+12X3+7X4+ 16X5+8X6+18X7+19X8

满足：

19X1+13X2+12X3+7X4+16X5+8X6+18X7 +19X8≤50

Xi =0或1（i=1，2，……，8）

由整数规划容易求得3组最优解：

（1，1，0，0，0，0，1，0）T

（0，1，1，1，0，0， 1，0）T

（1，0，1，0，0，0，0，1）T

这3组最优解都充分利用了货车的运载能力，是合理配装问题的最优解。但是无论采用哪一组最优解，都会有一些货物没有被运出。

该问题的合理配送：

在上述合理配装的三组最优解中任意选用其中一个优化解。

设选用第一个优化解（1，1，0，0，0，0， 1，0）T则剔除第1、2、7件货物后，用余下的货物重新建模如下：

MAXf（X）=12X3+7X4+16X5+8X6 +19X8

满足：

12X3+7X4+16X5+8X6+19X8≤50

Xi=0或1（i=3，4，5，6，8）

用优化方法求解，得到优化解：

（X3，X4，X5，X6，X8）T=（0，1，1，1，1）T

至此，只剩下货物X3没有装运。由于货物X3只有12吨，因此可以选项用一辆载重量较小的车辆进行单独将运。

最后，我们得到该实例的合理配送方案是两辆50吨货车和一辆12吨货车，一辆50吨货车装运货物X1，X2，X7，另一辆50吨货车装运货物X4，X5，X6，X8，而12吨货车装运货物X3。

在解决装货问题时，若所提供车辆的载重量是单一的，而由于载重量的限制会使某些货物无法与其它货物一起配装。显然，这些少量剩余的货物如仍采用这种车辆装运将是不经济的。因此，从成本优化的思想出发，提供装运货物的服务公司应配备不同吨位的车辆，这样将有利于降低营运成本。

在本文合理配送实例中，解决此类问题的方法可适用于多件货物运送问题。因为0-1整数规划中，变量的取值只有0（不装运）和1（装运），所以可根据不同问题改变PK及WK，以解决多件货物的运送问题。例如，某一客户需运送3类货物，每类货物均有4件，如果这些货物可以混装，那么就可以把每类货物的，而非每件货物的；如果某类货物和另一类货物不能混装，则需添加约束条件，以确保当此类货物变量取1时，另一类货物变量均取0。另外，在此类问题的数学模型中，货物的价值系数PK可以认为是货物重量WK的比例函数。在本文实例中，PK与WK的比例系数是1。若在其它问题中，它们的比例系数发生变化，则应分别代入进行计算，但不会对求解步骤产生影响。

通过以上实例证明，在物流配送过程中，建模优化求解方法能够较好地、较简单地解决合理配送问题，合理选择配送路线和对货物进行合理配装对于提高配送效率，降低运营成本具有重要意义。

参考文献：

1、吴清一.物流实物[M].中国物资出版社,2005.

2、姜宏.物流运输技术与实务[M].人民交通出版社,2002.

3、朱隆亮,谭任绩.物流运输组织管理[M].机械工业出版社,2004.

4、吴清一．现代物流概论[M].中国物资出版社,2003.

（作者单位：福建经济管理干部学院）

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”