物流运输-网络流问题最小化成本

行业背景

物流运输是供应链管理的关键,往往涉及到运输、仓储、装卸、配送等。如何合理的安排运输方案以提高货物运输的效率和可靠性,降低物流成本。这个优化问题也可以运用数学规划的方法来建模和求解。

例如:某企业需要将工厂生产的产品,运送至配送中心,再发往各个仓库,每个产品送往不同仓库所需的费用也不同,并且每条运输线路均有运送上限,如何安排运输,使运配送成本最低。

image.png

业务调研、数据量化、数学建模

在使用优化技术的时候,需要更详细的调研业务的需求,整理相关的业务逻辑和数据,并量化表示它。然后采用数学规划的方法进行数学建模。

此部分细节较多,可在案例物流运输中查阅细节,此处我们仅列出数学公式如下,参数部分请点击案例链接查看:

image.svg

其中s代表每个地址能提供的商品,d代表每个地点需要的商品,i和j代表一段通道的起点和终点,k代表中间站点。

以上公式对应的约束有:

  1. 每个地点提供的商品数量加上运入该点的商品之和等于该地其商品需求加上该地运出的商品数量之和

  2. 每条运输路线均有运送上限

源代码

MindOpt支持多种编程语言或者建模语言来调用。此处仅列出一种供参考:

MindOpt APL建模语言调用

MindOpt APL建模语言的源代码(可在物流运输上试运行):

##====MindOpt APL 建模语言版本代码====

clear model;

# 建模-------
# net2.mapl
# 数据
set CITIES := {"HN", "NE", "SE", "LN", "JL", "HLJ", "JS", "ZJ"} ;

set LINKS := {<"HN", "NE">, <"HN", "SE">, <"NE", "LN">, <"NE","JL">, <"NE","HLJ">, <"SE","LN">, <"SE","JL">, <"SE", "JS">, <"SE", "ZJ">};

param supply[CITIES] := <"HN"> 450 default 0;

param demand[CITIES] := <"JS"> 90,  <"ZJ"> 70, <"JL"> 120,  <"LN"> 120, <"HLJ"> 50 default 0;

set C := {"cost", "capacity"};

param data[LINKS * C] :=
            | "cost",  "capacity"|
|"HN", "NE" |    3.5,    250    |
|"HN", "SE" |    2.5,    250    |
|"NE", "LN" |    1.5,    100    |
|"NE", "JL" |    1.7,    100    |
|"NE", "HLJ"|    2.0,    100    |
|"SE", "LN" |    2.6,    100    |
|"SE", "JL" |    2.7,    100    |
|"SE", "JS" |    1.3,    100    |
|"SE", "ZJ" |    1.5,    100    |;

# 检查数据是否填正确
forall {<i> in CITIES } check supply[i] >= 0;
forall {<i> in CITIES } check demand[i] >= 0;
check sum {<i> in CITIES } supply[i] >= sum {<j> in CITIES} demand[j]; #供给大于需求

# 模型
var Ship[<i, j> in LINKS] >= 0 <= data[i, j, "capacity"];

minimize Total_Cost: sum {<i, j> in LINKS } data[i, j, "cost"] * Ship[i, j];

subto Balance: 
   forall {<k> in CITIES }
       supply[k] + sum {<i, k> in LINKS} Ship[i, k] >= demand[k] + sum {<k, j> in LINKS} Ship[k,j]; #每个站点供给都满足了需求


print "-----------------用MindOpt求解---------------";
option solver mindopt;     # (可选)指定求解用的求解器,默认是MindOpt
#option mindopt_options 'print=0'; #设置求解器输出级别,减少过程打印
solve;         # 求解

print "-----------------Display---------------";
display;        # 展示结果
print "经过优化后,最低运输成本=" , sum {<i, j> in LINKS } data[i, j, "cost"] * Ship[i, j];

结果和结果用法

不同代码日志打印不一样。部分结果日志打印如下所示:

...
Model summary.
 - Num. variables     : 9
 - Num. constraints   : 5
 - Num. nonzeros      : 15
 - Bound range        : [5.0e+01,4.5e+02]
 - Objective range    : [1.3e+00,3.5e+00]
 - Matrix range       : [1.0e+00,1.0e+00]
...
Simplex method terminated. Time : 0.008s


OPTIMAL; objective 2123.00
...
-----------------结果---------------
经过优化后,最低运输成本=2123

目标的最优解是:2123。更多解的细节,如决策变量的取值、验证约束是否正确,可以通过print命令打印来显示,变量的取值也可以从程序运行写的.sol文件里面获取,还可以调用display获取所有变量的取值。

如运行如下指令,验证“每个地点提供的商品数量加上运入该点的商品之和等于该地其商品需求加上该地运出的商品数量之和”这个约束:

forall {<k> in CITIES } 
 print '{}站点提供的商品数量与运入该站点的商品数量之和为{}'%k ,
 supply[k] + sum {<i, k> in LINKS} Ship[i, k];
print "-------------------";    
forall {<k> in CITIES } 
 print '{}站点需要的商品数量与运出该站点的商品数量之和为{}'%k ,
 demand[k] + sum {<k, j> in LINKS} Ship[k,j];

结果如下:

HN站点提供的商品数量与运入该站点的商品数量之和为450
NE站点提供的商品数量与运入该站点的商品数量之和为250
SE站点提供的商品数量与运入该站点的商品数量之和为200
LN站点提供的商品数量与运入该站点的商品数量之和为120
JL站点提供的商品数量与运入该站点的商品数量之和为120
HLJ站点提供的商品数量与运入该站点的商品数量之和为50
JS站点提供的商品数量与运入该站点的商品数量之和为90
ZJ站点提供的商品数量与运入该站点的商品数量之和为70
-------------------
HN站点需要的商品数量与运出该站点的商品数量之和为450
NE站点需要的商品数量与运出该站点的商品数量之和为250
SE站点需要的商品数量与运出该站点的商品数量之和为200
LN站点需要的商品数量与运出该站点的商品数量之和为120
JL站点需要的商品数量与运出该站点的商品数量之和为120
HLJ站点需要的商品数量与运出该站点的商品数量之和为50
JS站点需要的商品数量与运出该站点的商品数量之和为90
ZJ站点需要的商品数量与运出该站点的商品数量之和为70

运行如下代码,将输出打印为csv格式,作为物流运输问题的解决方案:

print "{},{},{} "% "起点","途径点","商品数量" : "Results.csv";
close "Results.csv";

forall {<i, j> in LINKS}
    print "{},{},{}" % i,j,Ship[i,j]  >> "Results.csv";

close "Results.csv";

结果如下:

image.png

即,从工厂运输商品到各个仓库的最低运输成本为2123。运输方案如下:

  • 从HN工厂运输到NE配送中心的商品数量为250,到SE配送中心是200;

    • 从NE配送中心运输到LN仓库的商品数量为100,到JL仓库为100,到HLJ仓库为50

    • 从SE配送中心运输到LN仓库的商品数量为20,到JL仓库是20,到JS仓库为90,到ZJ仓库为70

      • LN仓库汇总了120的商品,JL汇总120,HLJ汇总50,JS汇总90,ZJ汇总70

        • 最后计算两个配送中心发往各个仓库的运输成本,即2123。

image.png