摘要:本文针对单产品、多工厂、多生产线、考虑生产线产能和客户需求时间窗的生产批量与运输联合优化问题算法进行了研究,基于贪婪思想设计了三阶段启发式算法。通过四组不同规模算例对算法进行了验证,结果表明,在保证求解质量前提下,启发式算法求解速度优于商业软件Gurobi求解速度,并且随着算例规模的增加,两者求解时间差在不断扩大。
关键词:生产批量;运输;联合优化;启发式算法;需求时间窗
1.引言
随着经济的全球化,市场上企业之间的竞争变得越来越激烈,逐渐由企业之间的竞争演变为供应链之间的竞争[1]。供应链管理主要涉及到四个领域:供应、生产计划、物流和需求。其中,生产计划与物流是企业生产管理的核心任务[2],物流是第三利润源泉[3]。生产计划与物流习惯性地统称为生产运输问题,它在整个供应链管理中处于核心地位,其功能的强弱影响到供应链上各企业能否平稳有序地进行生产。
企业在做生产运输决策时进行顺序决策,或者凭着经验进行联合决策[4],这样的决策往往达不到最优,为此,许多学者对各种情况下的生产运输联合优化问题进行了研究。Daganzo[5]分析了一个产地,多个销地的生产配送同步问题,并且考虑了库存成本,最后证明了生产运输同步配送要比独立决策所产生的生产运输成本更少。Daganzo 在文章中没有考虑交货日期,只是单纯对独立决策和联合决策进行了比较。
Stecke & Zhao[6]考虑了到货期的情况,研究了制造公司的生产和运输的集成,该公司在按订单生产模式生产定制产品,并施行第三方物流外包模式。公司通过在可能的情况下为每个订单选择慢速运输模式来减少为所有已履行订单支付的总运输成本。
Geismar等[7]研究了生产和运输联合调度问题的一种变体,其中涉及到了保质期短的产品,没有产品库存。在满足客户需求的情况下,以完成生产和交付产品所需的最短时间为目标。
Guo等[8]研究了MTO供应链(Make to Order Supply Chain)中集成生产与运输调度问题,建立了基于和声搜索的模拟优化模型,给出了求解该问题的启发式算法。提出了一种新的改进技巧,提高了寻优性能。
Frazzon等[9]提出了一种用于供应链上生产和运输过程集成调度的混合方法。该方法结合了混合整数线性规划、离散事件模拟和遗传算法。
Guo等人[10]考虑全球供应链环境下生产与绿色运输的协调问题,以及生产与运输的协调对供应链可持续性的影响。考虑到订单处理复杂,发货时间固定,绿色运输和多种运输方式等因素,制定了不同的运输模式,包括空气,海洋和陆地运输的碳排放量的测量,并提出了一种基于混合遗传算法的优化方法求解模型。
Adulyasak & Cordeau[11]引入多车辆生产路径问题和库存路径问题公式,以解决在最大水平(ML)和订单到达水平(OU)库存补充策略下的问题。
杨志林等[12]考虑随机需求下单供应商和多零售商的生产-库存-运输联合优化问题。由供应商统一决策各零售商的送货量和送货时间,并基于此建立单供应商与多零售商的生产-库存-运输优化模型。
Miranda等[13]提出了一个混合整数规划模型,以集成生产,库存,分销和配送决策在一个单一的框架。考虑一个场景,其中只有一条生产线和一辆车分别可用于生产产品和交付最终产品。
Darvish等[4]研究了考虑客户时间窗和订单需求量的选址、生产、库存和运输联合优化决策问题,以总成本极小化为目标建立混合整数规划模型。
Tas等[14]研究了准备时间和加班时间随机的有容量限制的生产批量问题,建立了顺序优化随机规划模型,设计了两种启发式算法求解问题。
Ou & Feng[15]针对容量可调整的单产品生产批量问题,设计了一种有效的多项式时间算法,验证了容量调整后的生产批量问题比原来问题节省成本。Moreira等[16]结合实际工业背景,研究了PRP(Production-Routing Problem)问题,针对大规模问题设计了三阶段算法,通过实例计算,证明了联合优化可以节省21.73%成本。
上述研究解决了实际中的一些问题,但还未发现有人研究单产品、多工厂、多生产线、考虑生产线产能和需求时间窗的生产批量与运输联合优化问题算法,本文针对该问题设计了三阶段启发式算法,并设计算例对算法进行了验证。
2.问题建模
2.1问题描述
某企业拥有一个总公司和多个位于不同省市的工厂,进行单一产品生产活动。全国不同地区客户在线向总公司下达订单,总公司将订单分配给不同工厂进行生产和交付活动。工厂每周二和周五进行排程,所以不同生产时段总的生产时间不同。工厂每条生产线有最大工作时间限制,因此,在一段时间内每个工厂产能有限。每个订单有其对应的交货期(需求时间窗),当一段时间内某个工厂无法完成某个订单的生产交付活动时,需要对该订单进行拆分处理,由多个工厂共同生产交付。订单分配到工厂后,工厂需要制定订单生产计划(由哪些生产线在哪些时段生产),产生生产成本和生产线启动成本(固定生产成本)。产品生产出来以后,如果未到交货期,则在工厂仓库内存储,产生库存成本;如果在交货期内,则可以根据实际情况决定是否将产品运输到订单需求地,产生运输成本。给定一段时间内各个客户点的订单需求量和每个订单对应的交货期,制定生产计划和运输调度方案,在规定的交货期内满足各个客户的订单需求,并且使生产费用、库存费用和运输费用之和最少。
2.2模型假设
对于生产运输联合优化问题,本文根据实际情况做出如下假设:
(1)整个生产计划期可以划分为若干个长度不相等的生产时段,偶时段最大工作时间为72小时,奇时段最大工作时间为96小时;
(2)制定生产计划之前,所有客户订单均为已知,即生产过程中顾客不会取消或修改订单,也不会再产生新的订单;
(3)所有生产线总的生产能力能够满足所有客户订单总需求;
(4)每个生产时段生产的产品如果直接运输给客户,则不需要支付存储费;如果存放在仓库中等待后续时段再安排运输,则会产生存储费用;
(5)不考虑从工厂到客户点的在途运输时间,假设任意工厂在任意时段生产的产品均可瞬间送达任意客户点。
2.3符号描述
为了便于模型的描述和建立,本文定义如下符号:
(1)索引
i工厂
l生产线
j订单
t生产时段
(2)集合
I工厂集合,I={1,2,…,m}
Li工厂i的生产线集合,Li={1,2,…,pli}
J订单集合,J={1,2,…,n}
T计划期内包含的所有生产时段序号集合,T={1,2,…,v}
Tj订单j的交货期内包含的生产时段序号集合,
Tj={tej,tej+1,……tlj},Tj?哿T,j∈J
(3)参数
qj订单j对应的产品需求量
tej订单j交货期内的第一个生产时段序号(最早生产时段序号)
tlj订单j交货期内最后一个生产时段序号(最晚生产时段序号)
pli工厂i拥有的生产线数量
capilt工厂i第l条生产线在生产时段的最大工作时间
capeil工厂i第l条生产线生产单位产品所耗时间
roi工厂i的初始库存
cri工厂i存储单位产品单位时段的库存成本
pil工厂i第条生产线对应的单位产品生产成本
fpil启用工厂i第l条生产线进行生产所产生的固定成本
tcij从工厂i运输单位产品到订单j需求地的运输成本
(4)决策变量:
silt工厂i第l条生产线在时段生产产品的数量
rit工厂i在t时段末产品的库存量
fijtt时段从工厂i运往订单j需求地的产品数量
xilt1,t时段使用工厂i的第l条生产线进行生产
0,否则
2.4数学模型
针对生产运输联合优化问题,建立以生产成本、库存成本和运输成本之和极小化为目标的混合整数规划模型,具体如下:
minz=■■■silt·pil+■■■xilt·fpil+■■rit·cri+■■■fijt·tcij (1)
silt·capeil≤xilt·capilt i∈I,l∈Li,t∈T (2)
ri,t-1+■silt=■fijt+rit i∈I,t∈T \{1} (3)
roi+■silt=■fijt+rit i∈I,t∈{1} (4)
fijt=0 i∈I,j∈J t∈T\Tj (5)
■■fijt=qj j∈J (6)
silt≥0 i∈I,l∈Li,t∈T (7)
rit≥0 i∈I,t∈T (8)
fijt≥0 i∈I,j∈J t∈T (9)
xilt∈{0,1} i∈I,l∈Li t∈T (10)
目标函数(1)表示极小化的总费用,总费用包括生产费用、库存费用和运输费用。
约束条件(2)表示每条生产线在每个时段的实际生产时间不能超过该生产线的可用工作时间,且如果某个时段不启用生产线,则产量为0;约束条件(3)和(4)表示每个工厂各个时段的生产量、库存量和需求量之间的平衡关系;约束条件(5)表示工厂在订单交货时间窗以外时刻向该订单运输产品数量为0;约束条件(6)表示各个工厂在订单交货时间窗内运输到该订单需求地产品数量之和等于订单所需要的产品数量。
约束条件(7)、(8)、(9)、(10)表示变量取值约束,其中生产量、库存量和运输量的取值与产品性质有关,有些产品需要取整数。
3.求解算法
本文设计了启发式算法对问题求解。启发式算法分为三个阶段,第一阶段根据交货期约束和生产线生产时间约束,基于贪婪思想制定初始生产计划和运输方案;为了减少不必要的存储费用,在第二阶段根据各个订单的交货时间窗,对初始生产和运输方案进行调整,获得新的生产和运输方案;第三阶段计算生产和运输环节产生的总费用。
本文后面采用的符号含义与上面建立模型过程中使用的符号含义一样,只是将索引放到了小括号中,如cap(i,l,j)。为了更加方便地描述算法,本节定义了一些新的参数符号:
ptc(i,l,j)表示工厂i中第l条生产线生产单位产品并运到订单j需求地所产生的成本;
re表示工厂i和生产线l的数组,用dim进行索引,比如1,2=re(1)表示数组re中第1组数据为工厂1和生产线2;
tt(i,l)表示工厂i中第l条生产线的日期,其初始值为0,比如tt(1,2)=4表示工厂1中第2条生产线的日期为4;
tu(i,l)表示工厂i中第l条生产线的日期,其初始值为v,比如tu(1,1)=7表示工厂1中第1条生产线的日期为7;
h(i,l,t1,j,t2)表示工厂i中第l条生产线在t1时期生产在t2时期运输到订单j需求地产品的数量;
inf表示一个无穷大的正数。
同时,定义了一些函数:
min()表示获取括号内数组最小值的索引集合,比如re=min(ptc(:,:,j))表示将数组ptc(:,:,j)中最小值的索引的集合赋予变量re,其中ptc(:,:,j)={ptc(i,l,j)|i∈I,l∈Li};
shape()表示获取括号内数组规模的大小,比如2,4=shape(re)表示数组re的规模为2×4维。2=shape(re)(1)表示数组规模的第一维规模为2。
3.1制定初始方案
预处理:将订单按照其交货时间窗截至日期进行排序,如果交货时间窗截止日期相同时,则按交货时间窗开始日期进行排序,当订单的交货时间窗完全相同时则对这些订单随机排序。
步骤1:判断是否完成了所有订单,如果没有,则转入步骤2,否则结束。
步骤2:判断订单j的需求量q(j)是否大于0,如果需求量q(j)大于0,令m_pl_number等于m与pl之积,转入步骤3,否则将j加1,转入步骤1。
步骤3:判断m_pl_number是否大于0,如果大于0,则执行re=min(ptc(:,:,j)),获得价格矩阵ptc中最小值索引的集合,再执行m_pl_number = m_pl_number - shape(re)(1),变化条件变量,转入步骤4,否则,将j加1,转入步骤1。
步骤4:判断索引dim是否小于等于数组re中的工厂i和生产线l的个数,如果是,则获得第dim对工厂i和生产线l的索引,转入步骤5,否则,转入步骤3。
步骤5:判断条件变量tt(i,l)的值是否小于等于订单j的最晚交货期tl(j),如果tt(i,l)小于等于tl(j),转入步骤6,否则,将价格矩阵ptc(i,l,j)的值赋为正无穷大,并将dim 的值加1,转入步骤4。
步骤6:判断条件变量tt(i,l)的值是否小于等于订单j最晚交货期tl(j),同时,判断订单j的需求量q(j)是否大于0,当这两者同时成立时通过公式cap(i,l,tt(i,l))//cape(i,l)将工厂i第l条生产线在tt(i,l)时期所能生产产品的最大数量赋予变量tem_num,转入步骤7,否则,依次将价格矩阵ptc(i,l,j)的值变为正无穷大,然后将dim的值加1,转入步骤4。
步骤7:判断订单j需求量q(j)是否大于等于tem_num,如果q(j)大于等于tem_num,转入步骤8,否则,转入步骤9。
步骤8:判断条件变量tt(i,l)是否大于等于订单j的最早交货日期te(j),如果是,将变量h(i,l,tt(i,l),j,tt(i,l))的值加tem_num,订单j需求量q(j)的值减去tem_num,工厂i第l条生产线在tt(i,l)时期可利用的生产时间减去tem_num*cape(i,l),再将tt(i,l)的值加1,转入步骤6;否则,将变量h(i,l,tt(i,l),j,te(j))的值加tem_num,订单j需求量q(j)的值减去tem_num,工厂i第l条生产线在tt(i,l)时期可利用的生产时间减去tem_num*cape(i,l),再将tt(i,l)的值加1,转入步骤6。
步骤9:判断tt(i,l)是否大于等于订单j的最早交货时间时期te(j),如果是,将变量h(i,l,tt(i,l),j,tt(i,l))的值加上订单j的需求量q(j),工厂i第l条生产线在tt(i,l)时期可利用的生产时间cap(i,l,tt(i,l))减去q(j)*cape(i,l),并将订单j的需求量q(j)变为0,转入步骤6;否则,将变量h(i,l,tt(i,l),j,te(j))加上订单j的需求量q(j),工厂i第l条生产线在tt(i,l)时期可利用的生产时间cap(i,l,tt(i,l))减去q(j)*cape(i,l),并将订单j的需求量q(j)变为0,转入步骤6。
3.2对初始方案进行调整,获得新的方案
当在规定的时期内某些生产线获得分配的产品数量较少时会产生不必要的存储成本,因此,有必要对初始方案进行调整,减少存储成本。为此,引入了新的变量,assign(i,l,j)=■■h(i,l,t2,j,t2),i∈I,l∈Li,j∈J。
因为订单已经排好顺序,随着订单序号的增加订单交货时间窗结束日期也在增加,所以本阶段从最后一个订单开始计算。
步骤1:判断是否已经完成第一个订单,如果是则结束计算,否则转入步骤2。
步骤2:判断是否遍历所有工厂,如果是则将j减1,转入步骤1,否则,转入步骤3。
步骤3:判断是否遍历所有生产线,如果是则将i加1,转入步骤2,否则,将订单j的最晚交货时期tl(j)赋予变量tu(i,j),然后转入步骤4。
步骤4:判断变量assign(i,l,j)的值是否大于0,如果大于0则通过执行公式tem_num1 = cap(i,l,tu(i,l))// cape(i,l)将工厂i中第l条生产线在tu(i,l)时期所能生产产品的最大数量赋予变量tem_num1,然后转入步骤5,否则将l加1,转入步骤3。
步骤5:判断变量assign(i,l,j)的值是否大于tem_num1,如果大于,则转入步骤6,否则,转入步骤7。
步骤6:判断变量tu(i,l)的值是否大于等于订单j的最早交货时期,如果大于,
将变量h1(i,l,tu(i,l),j,tu(i,l))的值增加tem_num1单位,将变量assign(i,l,j)的值减少tem_num1单位,变量cap(i,l,tu(i,l))的值减少tem_num1*cape(i,l)单位,将tu(i,l)的值减少1,再转入步骤4;否则,将变量h1(i,l,tu(i,l),j,te(j))的值增加tem_num1单位,将变量assign(i,l,j)的值减少tem_num1单位,变量cap(i,l,tu(i,l))的值减少tem_num1*cape(i,l)单位,将tu(i,l)的值减少1,再转入步骤4。
步骤7:判断变量tu(i,l)的值是否大于等于订单j的最早交货时期,如果大于,将变量h1(i,l,tu(i,l),j,tu(i,l))的值增加assign(i,l,j)单位,变量cap(i,l,tu(i,l))的值减少assign(i,l,j)*cape(i,l)单位,将变量assign(i,l,j)的值变为0,再转到step4;否则,将变量h1(i,l,tu)i,l),j,te(j))的值增加assign(i,l,j)单位,变量cap(i,l,tu(i,l))的值减少assign(i,l,j)*cape(i,l)单位,将变量assign(i,l,j)的值变为0,再转到步骤4。
3.3计算费用
通过第二阶段的调整,本文获得了较好的生产运输方案,所以在第三阶段本文对第二阶段得到的生产运输方案进行费用计算,主要包括生产费用s_cost、固定生产费用fp_cost、库存费用r_cost、运输费用tc_cost。
步骤1:计算生产变量和运输变量
在第二阶段,本文得到了一个生产运输整数变量h1(i,l,t1,j,t2),i∈I,l∈Li,j∈J,i∈I,l∈Li,t2∈T,通过以下公式可以求出生产变量和运输变量。
s(i,l,t1)=■■h1(i,l,t1,j,t2),i∈I,l∈Li,t1∈T (11)
通过公式(11)的计算得到生产变量s,s(i,l,t)表示工厂i中第l条生产线在t时期生产产品的数量。
f(i,j,t2)=■■hl(i,l,t1,j,t2) i∈I,j∈J,t2∈T (12)
通过公式(12)的计算得到运输变量f,f(i,j,t)表示工厂i中在t时期运输到订单j需求地产品的数量。
步骤2:计算库存变量和固定生产变量
已知初始库存为0,又求出了生产方案和运输方案,根据公式(3)和(4)可以求出库存方案r。
ri,t-1+■silt=■fijt+rit i∈I,t∈T\{1} (3)
roi+■silt=■fijt+rit i∈I,t∈{1} (4)
其中r(i,t)表示工厂i在t时期末的库存量。
已知生产变量的值,通过公式(2)可以得到固定生产变量的值。
silt·capeil≤xilt·capeilt (2)
其中x(i,l,t)表示工厂i中第l条生产线在t时期是否进行生产活动。
步骤3:计算各项费用及总费用
已知生产变量、固定生产变量、库存变量和运输变量的值,可以分别求出生产费用、固定生产费用、库存费用和运输费用。根据求出的各项费用,可以求出产品从工厂生产到产品运输到订单需求地的总费用。
求解模型的启发式算法总流程图如图1所示。
图1 启发式算法总流程图
4.数据实验与分析
4.1 实验环境与数据
为验证模型和算法的有效性,本文根据调研某央企的真实数据按一定规则生成初始数据。根据工厂数量、每个工厂生产线数量、订单数量、生产时段数量设计了四种不同规模的算例对算法进行验证,并设计了五组数据,验证了库存费用和固定生产费用对算法性能的影响。四组不同规模参数如表1所示,其余参数服从均匀分布或离散分布,具体见表2。
表1 四组不同规模算例参数
注:0.0576=(144/1000)*0.4,其中单位产品质量为144kg,1吨产品单位公里运输费用为0.4元
本文利用Python语言编写启发式算法代码,根据一定规则生成符合实际的随机数,在电脑(Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz 2.7GHz RAM 8.00 GB)上运行程序。
4.2 实验结果与分析
每组规模数据随机产生100个算例,通过比较解的近似程度以及算法运行时间差来比较算法的性能,运行结果如表3所示。
表3 不同规模算例运行结果表
从表3可以看出,当算例规模较小时Gurobi软件和启发式算法运行时间差较小。随着算例规模的增加,虽然启发式算法解的质量在下降,但整体保持在较高的水平,而两种求解方式运行时间差在不断扩大。由此可以看出,随着算例规模的扩大,在求解速度方面,启发式算法相较于商业软件具有更大的优势。
为研究库存成本与固定生产费用对算法性能的影响,本文设计了5组数据进行模拟计算,每组数据同样运行100次,运行结果如表5所示。
表5 不同参数运行结果表
在表5中,比较1、2、3组数据可以看出,随着库存费用的增加,启发式算法解的质量在变差,但精确解与其平均比值仍然保持在0.98以上,而Gurobi与启发式算法运行时间差则有所增加。比较1、4、5组数据可以看出,随着固定生产费用的增加,启发式算法解的质量没有变化,精确解与其平均比值为0.992,Gurobi与启发式算法运行时间差有所增加。
5.结语
生产计划与运输问题是供应链中的一个重要问题,目前大多数研究主要集中生产计划问题及其延伸问题,少部分人在研究生产与运输联合优化。本文在充分考虑了生产计划和运输问题相关特征基础上,同时考虑多工厂、多生产线、产能限制、需求时间窗等因素,以生产成本、库存成本和运输成本之和极小化为目标建立混合整数规划模型。在模型的求解方面,本文设计了三阶段启发式算法,在第一阶段根据单位生产成本和运输成本对订单进行分配,获得初始的生产计划和运输方案;在第二阶段,为减少库存成本,对初始生产计划和运输方案进行调整,尽量在客户对应的需求时间窗内生产运输该客户的产品;第三阶段,根据第二阶段的生产计划和运输方案计算这两个环节产生的总费用。实验结果表明,本文提出的算法在保证求解质量前提下,有效地缩短了求解时间,能够对考虑需求时间窗的多工厂多生产线且有容量约束的生产运输联合优化问题起指导作用。C
(作者单位:北京物资学院信息学院)
参考文献
[1] 肖迪. 基于结构分析的供应链之间竞争行为的研究[D]. 上海交通大学, 2008.
[2] 苏生. 多工厂生产计划与调度优化模型与求解算法[D]. 哈尔滨工业大学, 2007.
[3] 葛岩, 包昆. 第三方物流对商业连锁企业核心竞争力的提升[J]. 华东经济管理, 2002(06):85-87.
[4] Darvish M , Coelho L C . Sequential versus integrated optimization: Production, location, inventory control, and distribution[J]. European Journal of Operational Research, 2018, 268(1):203-214.
[5] Blumenfeld D E, Burns L D, Daganzo C F. Synchronizing production and transportation schedules[J]. Transportation Research Part B Methodological, 1991, 25(25):23-37.
[6] Stecke K E, Zhao X. Production and Transportation Integration for a Make-to-Order Manufacturing Company with a Commit-to-Delivery Business Mode[J]. Manufacturing & Service Operations Management, 2008, 9(2):206-224.
[7] Geismar H N, Laporte G, Lei L, et al. The Integrated Production and Transportation Scheduling Problem for a Product with a Short Lifespan[J]. Informs Journal on Computing, 2008, 20(1):21-33.
[8] Guo Z, Shi L, Chen L, et al. A harmony search-based memetic optimization model for integrated production and transportation scheduling in MTO manufacturing[J]. Omega, 2017, 66:327-343.
[9] Frazzon E M, Albrecht A, Pires M, et al. Hybrid approach for the integrated scheduling of production and transport processes along supply chains[J]. International Journal of Production Research, 2018(1):1-17.
[10] Guo F, Liu Q, Liu D, et al. On Production and Green Transportation Coordination in a Sustainable Global Supply Chain[J]. Sustainability, 2017, 9(11):2071.
[11] Adulyasak Y, Cordeau J, Jans R. Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems[J]. Informs Journal on Computing, 2014, 26(1):103-120.
[12] 杨志林, 李擎卿, 林冠男. 随机需求下单供应商与多零售商的生产—库存—运输联合优化模型[J]. 大学数学, 2015, 31(5):12-19.
[13] Miranda P L, Morabito R, Ferreira D. Optimization model for a production, inventory, distribution and routing problem in small furniture companies[J]. TOP, 2018, 26(1):1-38.
[14] Ta? D, Gendreau M, Jabali O, et al. A capacitated lot sizing problem with stochastic setup times and overtime[J]. European Journal of Operational Research, 2019, 273(1):146-159.
[15] Ou J W, Feng J J. Production lot-sizing with dynamic capacity adjustment[J]. European Journal of Operational Research, 2019, 276(1):261-269.
[16] Moreira F N, Lobo B A, Cordeau J F, L Guimar?es,et al. Solving a large multi-product production-routing problem with delivery time windows[J]. Omega, 2019, 86, 154-172.