Low-carbon multimodal transportation path optimization based on multi-objective fuzzy chance-constrained programming

doi:10.11772/j.issn.1001-9081.2021122085

Abstract

Abstract:

Aiming at the optimization problem of multimodal transportation path optimization under the uncertainty of time window and demand， trapezoidal fuzzy numbers were used to express fuzzy demand and fuzzy time window， and a multi-objective fuzzy chance-constrained model was established considering carbon emission costs， transportation costs， and customer satisfaction. The fixed crossover and mutation probabilities will directly affect the convergence of the algorithm. For this problem， the adaptability was combined with the Non-dominated Sorting Genetic Algorithm-Ⅱ （NSGA-Ⅱ）， and the effectiveness of the proposed model and algorithm was verified by comparing them with DOCPLEX and NSGA-Ⅱ. Finally， the influence of changes in carbon tax and fuzzy demand preference value on optimization results were explored. The research results show that the proposal of carbon tax can effectively promote “road-to-rail transportation and road-to-water transportation” significantly， thereby reducing carbon emissions. But too high carbon tax does not necessarily reduce carbon emissions， and also causes excessive costs to enterprises. And the increase of fuzzy demand preference value will lead to the increase of total cost， which means that transportation economy and reliability cannot be obtained at the same time. Therefore， setting reasonable carbon tax and fuzzy demand preference value is an effective way to improve the environmental benefit and transportation benefit of multimodal transportation.

Key words: multimodal transportation, path optimization, trapezoidal fuzzy number, carbon tax, fuzzy chance-constrained model, adaptive NSGA-Ⅱ

摘要：

针对时间窗与需求量不确定性下的多式联运路径优化问题，运用梯形模糊数表示模糊需求量与模糊时间窗，并考虑碳排放成本、运输成本以及客户满意度，建立了多目标模糊机会约束模型。固定的交叉、变异概率会直接影响算法的收敛性，针对此问题，将自适应性与非支配排序遗传算法Ⅱ（NSGA-Ⅱ）结合，并通过与DOCPLEX和NSGA-Ⅱ的对比验证了所提模型与算法的有效性。最后，探究了碳税值与模糊需求量偏好值的变化对优化结果的影响。研究结果表明：碳税值的提出可有效促进“公转铁、公转水”，从而显著减少碳排放量，然而过高的碳税值并不一定意味着碳排放量的减少，还会对企业造成过高的成本；模糊需求量偏好值的提高会造成总成本的增加，意味着运输经济性与可靠性两者不可兼得。因此，合理设置碳税值与模糊需求量偏好值是提高多式联运环保效益与运输效益的有效方式。

关键词: 多式联运, 路径优化, 梯形模糊数, 碳税值, 模糊机会约束模型, 自适应非支配排序遗传算法Ⅱ

CLC Number:

TP301.6

Min ZHANG, Xiaolong HAN. Low-carbon multimodal transportation path optimization based on multi-objective fuzzy chance-constrained programming[J]. Journal of Computer Applications, 2023, 43(2): 636-644.

张敏, 韩晓龙. 多目标模糊机会约束规划的低碳多式联运路径优化[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 636-644.

Figures/Tables 21

Fig. 1 Multimodal transportation network

Tab. 1 Parameter description

参数	说明
$N$	运输网络节点集合 $(i, j ∈ N)$
$L$	中间节点集合
$M$	运输方式集合
$O$	运输任务的起点
$D$	运输任务的终点
$A m$	运输方式 $m$ 的固定费用
$V m$	运输方式 $m$ 的平均行驶速度
$ρ$	碳税值
$T j$	货物到达节点j的时间
$S A$	客户对送达时间的满意度
$β$	最低客户满意度
$e m$	运输方式 $m$ 的单位碳排放量
$e ˜ = (e 1, e 2, e 3, e 4)$	客户的模糊需求量
$C m$	运输方式 $m$ 的单位运输成本
$d i j m$	采用运输方式 $m$ ，节点 $i, j$ 之间的运输距离
$c o m l$	运输方式由 $m$ 转换为l的过程中的单位碳排放量
$h m l$	运输方式由 $m$ 转换为l的中转成本
$T m l$	运输方式由 $m$ 转换为l的中转时间
$E E T$	客户能够容忍货物到达的最早时间
$L L T$	客户能够容忍货物到达的最晚时间
$E T$	客户最期待货物到达的最早时间
$L T$	客户最期待货物到达的最晚时间

Tab. 1 Parameter description

参数	说明
$N$	运输网络节点集合 $(i, j ∈ N)$
$L$	中间节点集合
$M$	运输方式集合
$O$	运输任务的起点
$D$	运输任务的终点
$A m$	运输方式 $m$ 的固定费用
$V m$	运输方式 $m$ 的平均行驶速度
$ρ$	碳税值
$T j$	货物到达节点j的时间
$S A$	客户对送达时间的满意度
$β$	最低客户满意度
$e m$	运输方式 $m$ 的单位碳排放量
$e ˜ = (e 1, e 2, e 3, e 4)$	客户的模糊需求量
$C m$	运输方式 $m$ 的单位运输成本
$d i j m$	采用运输方式 $m$ ，节点 $i, j$ 之间的运输距离
$c o m l$	运输方式由 $m$ 转换为l的过程中的单位碳排放量
$h m l$	运输方式由 $m$ 转换为l的中转成本
$T m l$	运输方式由 $m$ 转换为l的中转时间
$E E T$	客户能够容忍货物到达的最早时间
$L L T$	客户能够容忍货物到达的最晚时间
$E T$	客户最期待货物到达的最早时间
$L T$	客户最期待货物到达的最晚时间

Tab. 2 Decision variables

变量	说明
$x i j m$	采用运输方式 $m$ ，从节点 $i$ 运输到 $j$ 时取1，否则取0
$y i m l$	在节点 $i$ ，运输方式由 $m$ 转换为 $l$ 时取1，否则取0

Tab. 2 Decision variables

变量	说明
$x i j m$	采用运输方式 $m$ ，从节点 $i$ 运输到 $j$ 时取1，否则取0
$y i m l$	在节点 $i$ ，运输方式由 $m$ 转换为 $l$ 时取1，否则取0

Fig. 2 Customer satisfaction function

Fig. 3 Fuzzy demand function

Fig. 4 Chromosome coding

Fig. 5 Fragment crossover

Fig. 6 Reverse mutation

Fig. 7 Flowchart of the proposed algorithm

Tab. 3 Transportation mode parameters

运输方式	公路	铁路	水路
公路	0； 0； 0	8；1；0.128	9； 2； 0.117
铁路	8； 1； 0.128	0； 0； 0	10； 3； 0.113
水路	9； 2； 0.117	10； 3； 0.113	0； 0； 0

Tab. 4 Parameters of different modes of transportation

运输

方式

平均速度/（km·h^-1）

单位费用/

（元·km^-1·t^-1）

固定费用/元

单位碳排量/

（kg·km^-1·t^-1）

Tab. 5 Order-related information parameters

任务序号	节点数	起点-终点	需求量/t	终点时间窗/h
1	10	1-10	［65，70，78，88］	［1，2，4，6］
2	20	1-20		［1，3，4，6］
3	30	1-30		［1，4，6，10］
4	40	1-40		［2，4，6，8］
5	50	1-50		［3，5，7，10］

Tab. 6 Comparison of solution results between DOCPLEX and adaptive NSGA-Ⅱ

网络节点数	DOCPLEX				自适应NSGA-Ⅱ				差距百分比/%
网络节点数	Z_1min	Z_2min	Z_3max	运行时间/s	Z₁	Z₂	Z₃	运行时间/s	gap1	gap2	gap3
10	3.562	3 060.80	1.000	0.788	4.014	3 325.96	0.962	1.524	12.69	8.66	4
20	3.385	3 736.96	1.000	6.048	3.913	3 955.20	1.000	5.991	15.60	5.84	0
30	7.229	8 081.52	1.000	20.420	8.066	8 452.54	1.000	16.284	11.58	4.59	0
40	2.682	5 125.95	1.000	50.220	3.487	5 599.38	1.000	21.843	30.01	9.24	0
50	5.075	7 525.76	1.000	92.644	6.133	8 143.89	0.985	32.977	20.85	8.21	2

Tab. 7 Comparison of solution results between NSGA-Ⅱ and adaptive NSGA-Ⅱ

网络节点数	自适应NSGA-Ⅱ				NSGA-Ⅱ				差距百分比/%
网络节点数	Z₁	Z₂	Z₃	运行时间/s	$Z 4$	$Z 5$	$Z 6$	运行时间/s	gap4	gap5	gap6
10	4.014	3 325.96	0.962	1.524	5.114	3 905.22	0.943	1.483	27.40	17.42	-2
20	3.913	3 955.20	1.000	5.991	4.753	4 478.25	0.970	5.786	21.47	13.22	-3
30	8.066	8 452.54	1.000	16.284	10.030	9 182.34	1.000	16.113	24.35	8.63	0
40	3.487	5 599.38	1.000	21.843	4.762	6 215.47	1.000	21.477	36.56	11.00	0
50	6.133	8 143.89	0.985	32.977	7.784	8 799.48	0.976	31.849	26.92	8.05	-1

Tab. 7 Comparison of solution results between NSGA-Ⅱ and adaptive NSGA-Ⅱ

网络节点数	自适应NSGA-Ⅱ				NSGA-Ⅱ				差距百分比/%
网络节点数	Z₁	Z₂	Z₃	运行时间/s	$Z 4$	$Z 5$	$Z 6$	运行时间/s	gap4	gap5	gap6
10	4.014	3 325.96	0.962	1.524	5.114	3 905.22	0.943	1.483	27.40	17.42	-2
20	3.913	3 955.20	1.000	5.991	4.753	4 478.25	0.970	5.786	21.47	13.22	-3
30	8.066	8 452.54	1.000	16.284	10.030	9 182.34	1.000	16.113	24.35	8.63	0
40	3.487	5 599.38	1.000	21.843	4.762	6 215.47	1.000	21.477	36.56	11.00	0
50	6.133	8 143.89	0.985	32.977	7.784	8 799.48	0.976	31.849	26.92	8.05	-1

Tab. 8 Transportation order parameters

订单号	起点-终点	需求量/t	终点时间窗/h
1	1-21	［50， 60， 65， 80］	［5， 10， 15， 20］
2	1-30	［155， 165， 176， 181］	［6， 11， 16， 21］
3	2-20	［180， 198， 210， 220］	［4， 8， 13， 18］
4	3-18	［60， 72， 86， 96］	［3， 8， 13， 17］
5	5-27	［118， 126， 140， 150］	［4， 10， 15， 19］
6	8-30	［208， 220， 230， 240］	［9， 11， 16， 20］
7	9-19	［105，110，118，138］	［3， 7， 12， 16］
8	12-22	［220， 228， 240， 250］	［3， 8， 12， 17］
9	14-16	［78， 88， 100， 115］	［2， 4， 7， 9］
10	15-28	［314， 325， 340， 350］	［4， 8， 12， 16］

Tab. 9 Solution results of different orders

订单号	路径	运输方式	满意度	碳排放成本/元	运输成本/元
1	1-20-21	公-公	0.977	35.500 0	1 031.366
2	1-21-26-30	公-公-公-公	1.000	103.620 0	9 983.371
3	2-20	公	0.956	88.923 0	2 229.934
4	3-19-18	公-公-公	1.000	37.170 0	1 072.427
5	5-17-28-27	公-公-公-公	1.000	74.977 0	2 080.320
6	8-10-2-11-18-30	公-公-公-公-公	1.000	130.943 0	3 741.217
7	9-12-19	公-公	1.000	48.473 3	1 349.793
8	12-18-22	公-公	1.000	104.297 0	2 720.021
9	14-19-16	公-公	1.000	27.873 0	844.126
10	15-2-28	公-公	1.000	149.427 0	3 827.744

Tab. 10 Routing results for each transport order under changes in carbon tax value

订单号	碳税值	路径	运输方式	订单号	碳税值	路径	运输方式
1	0~0.05	1-20-21	公-公	6	0~0.05	8-10-2-11-18-30	公-公-公-公-公
	0.1	1-20-21	公-公		0.1	8-12-30	公-水
	0.3	1-15-25-21	公-公-水		0.3	8-22-30	水-水
	0.5~0.7	1-7-21	水-铁		0.5~0.7	8-13-30	水-水
	0.9~1.1	1-5-21	水-铁		0.9~1.7	8-27-30	水-水
	1.3~1.9	1-10-21	水-水		1.9	8-9-30	水-水
2	0~0.05	1-21-26-30	公-公-公-公	7	0~0.05	9-12-19	公-公
	0.1	1-24-30	水-公		0.1	9-11-26-19	公-公-公
	0.3~0.5	1-29-30	水-水		0.3~0.5	9-27-19	水-公
	0.9~1.9	1-23-30	水-水		0.7	9-18-19	公-水
3	0~0.05	2-20	公		0.9~1.1	9-24-19	水-铁
	0.1	2-28-20	公-公		1.3~1.9	9-13-19	铁-铁
	0.3	2-12-20	公-水	8	0~0.05	12-18-22	公-公
	0.5	2-24-20	公-水		0.1	12-8-2-22	公-公-公
	0.7	2-18-20	公-水		0.3~0.5	12-23-22	铁-铁
	0.9	2-5-20	公-水		0.7~0.9	12-24-22	铁-铁
	1.1~1.9	2-26-20	水-铁		1.1~1.9	12-5-13-22	公-铁-水
4	0~0.05	3-19-18	公-公	9	0~0.05	14-19-16	公-公
	0.1	3-30-18	公-公		0.1	14-11-16	公-公
	0.3~0.5	3-9-18	水-公		0.3	14-18-3-16	公-公-公
	0.7	3-26-9-18	公-公-水		0.5~0.9	14-10-16	铁-公
	0.9	3-16-18	公-铁		1.1~1.3	14-22-28-16	铁-铁-铁
	1.1	3-5-18	铁-铁		1.5~1.9	14-9-16	铁-公
	1.3	3-8-18	铁-铁	10	0~0.05	15-2-28	公-公
	1.5~1.9	3-2-14-18	铁-铁-水		0.1~0.5	15-14-28	水-铁
5	0~0.05	5-17-28-27	公-公-公		0.7~1.9	15-12-29-28	铁-铁-铁
	0.1	5-11-14-27	公-公-公
	0.3	5-6-14-27	公-公-水
	0.5	5-23-27	铁-铁
	0.7	5-28-27	水-铁
	0.9	5-8-27	水-铁
	1.1~1.3	5-4-27	水-铁
	1.5~1.9	5-6-27	铁-水

Fig. 8 Frequency change of transportation mode

Fig. 9 Carbon emission change

Fig. 10 Total cost change

Fig. 11 Relationship between total cost and fuzzy demand preference value

References 23

1	PIECYK M I， McKINNON A C. Forecasting the carbon footprint of road freight transport in 2020［J］. International Journal of Production Economics， 2010， 128（1）： 31-42. 10.1016/j.ijpe.2009.08.027
2	FIGLIOZZI M， SAENZ J， FAULIN J. Minimization of urban freight distribution lifecycle CO2e emissions： results from an optimization model and a real-world case study［J］. Transport Policy， 2020， 86：60-68. 10.1016/j.tranpol.2018.06.010
3	CARIS A， MACHARIS C， JANSSENS G K. Decision support in intermodal transport： a new research agenda［J］. Computers in Industry， 2013， 64（2）：105-112. 10.1016/j.compind.2012.12.001
4	张旭，袁旭梅，降亚迪. 需求与碳交易价格不确定下多式联运路径优化［J］. 系统工程理论与实践， 2021， 41（10）：2609-2620. 10.12011/SETP2020-0231
	ZHANG X， YUAN X M， JIANG Y D. Optimization of multimodal transportation under uncertain demand and stochastic carbon trading price［J］. Systems Engineering - Theory and Practice， 2021， 41（10）：2609-2620. 10.12011/SETP2020-0231
5	FAHIMNIA B， SARKIS J， CHOUDHARY A， et al. Tactical supply chain planning under a carbon tax policy scheme： a case study［J］. International Journal of Production Economics， 2015， 164：206-215. 10.1016/j.ijpe.2014.12.015
6	蒋琦玮，林艺，冯芬玲. 模糊时间下考虑碳税值变化的多式联运路径优化问题研究［J］. 工业技术经济， 2020， 39（4）：81-88. 10.3969/j.issn.1004-910X.2020.04.010
	JIANG Q W， LIN Y， FENG F L. Research on multimodal transport path optimization problem considering carbon tax value changes under fuzzy time［J］. Journal of Industrial Technological Economics， 2020， 39（4）：81-88. 10.3969/j.issn.1004-910X.2020.04.010
7	LIAO C H， TSENG P H， LU C S. Comparing carbon dioxide emissions of trucking and intermodal container transport in Taiwan［J］. Transportation Research Part D： Transport and Environment， 2009， 14（7）：493-496. 10.1016/j.trd.2009.05.002
8	PIZZOL M. Deterministic and stochastic carbon footprint of intermodal ferry and truck freight transport across scandinavian routes［J］. Journal of Cleaner Production， 2019， 224：626-636. 10.1016/j.jclepro.2019.03.270
9	蒋玲茜，张培林，陈沿伊. 基于碳排放考量的集装箱海陆多式联运模式选择［J］. 水运管理， 2018， 40（1）：7-10， 13. 10.3969/j.issn.1000-8799.2018.01.003
	JIANG L Q， ZHANG P L， CHEN Y Y. Selection of container sea-land multimodal transportation mode based on carbon emission considerations［J］. Shipping Management， 2018， 40（1）：7-10， 13. 10.3969/j.issn.1000-8799.2018.01.003
10	CHENG R W， GEN M， TOZAWA T. Vehicle routing problem with fuzzy due-time using genetic algorithms［J］. Journal of Japan Society for Fuzzy Theory and Systems， 2017， 7（5）：1050-1061.
11	李晶，邵倩. 考虑多模糊时间窗医药物流配送路径优化［J］. 物流技术， 2020， 39（3）：89-93. 10.3969/j.issn.1005-152X.2020.03.018
	LI J， SHAO Q. Optimization of pharmaceutical logistics distribution route considering multiple fuzzy time windows［J］. Logistics Technology， 2020， 39（3）：89-93. 10.3969/j.issn.1005-152X.2020.03.018
12	GONCALVES G， HSU T， XU J. Vehicle routing problem with time windows and fuzzy demands： an approach based on the possibility theory［J］. International Journal of Advanced Operations Management， 2009， 1（4）：312-330. 10.1504/ijaom.2009.031247
13	彭勇，肖云鹏，罗义娟. 不确定环境下多式联运路径多目标优化［J］. 重庆交通大学学报（自然科学版）， 2021， 40（10）：154-160， 170. 10.3969/j.issn.1674-0696.2021.10.18
	PENG Y， XIAO Y P， LUO Y J. Multi-objective optimization for multi-modal transportation routing in uncertain environment［J］. Journal of Chongqing Jiaotong University （Natural Science）， 2021， 40（10）： 154-160， 170. 10.3969/j.issn.1674-0696.2021.10.18
14	耿娜娜，何燕，高海瑛，等. 不确定条件下的物流运输路径优化研究——以中欧班列多式联运为例［J］. 物流工程与管理， 2021， 43（10）： 112-115.
	GENG N N， HE Y， GAO H Y， et al. Research on optimization of logistics transportation route under uncertainty — taking China-Europe express multimodal transport as an example［J］. Logistics Engineering and Management， 2021， 43（10）： 112-115.
15	SHI Y， BOUDOUH T， GRUNDER O. A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand［J］. Expert Systems with Applications， 2017， 72： 160-176. 10.1016/j.eswa.2016.12.013
16	谢静，林国龙，何红弟，等. 模糊需求环境下考虑碳成本的多式联运路径优化［J］. 宁夏大学学报（自然科学版）， 2017， 38（2）：173-179. 10.3969/j.issn.0253-2328.2017.02.011
	XIE J， LIN G L， HE H D， et al. Optimization of multimodal transportation in fuzzy demand condition with consideration of carbon cost［J］. Journal of Ningxia University （Natural Science Edition）， 2017， 38（2）：173-179. 10.3969/j.issn.0253-2328.2017.02.011
17	SUN Y， LIANG X， LI X Y， et al. A fuzzy programming method for modeling demand uncertainty in the capacitated road-rail multimodal routing problem with time windows［J］. Symmetry， 2019， 11（1）： No.91. 10.3390/sym11010091
18	张晓楠，范厚明. 带时间窗偏好的多行程模糊需求车辆路径优化［J］. 计算机集成制造系统， 2018， 24（10）：2461-2477. 10.13196/j.cims.2018.10.009
	ZHANG X N， FAN H M. Optimization for multi-trip vehicle routing problem with fuzzy demands considering time window preference［J］. Computer Integrated Manufacturing Systems， 2018， 24（10）：2461-2477. 10.13196/j.cims.2018.10.009
19	刘艳芳. 考虑模糊需求的多式联运路径优化研究［D］. 北京：北京交通大学， 2016：21-23. 10.7666/d.Y3126098
	LIU Y F. Study on the multimodal routing optimization with fuzzy customer demands［D］. Beijing： Beijing Jiaotong University， 2016： 21-23. 10.7666/d.Y3126098
20	YAN S， ZHANG G J， HONG Z J， et al. How uncertain information on service capacity influences the intermodal routing decision： a fuzzy programming perspective［J］. Information， 2018， 9（1）： No.24. 10.3390/info9010024
21	FAZEL-ZARANDI M H， HEMMATI A， DAVARI S. The multi-depot capacitated location-routing problem with fuzzy travel times［J］. Expert Systems with Applications， 2011， 38（8）： 10075-10084. 10.1016/j.eswa.2011.02.006
22	荆巍巍，章磊，田俊. 基于自适应NSGA-Ⅱ算法的柔性车间多目标生产调度［J］. 组合机床与自动化加工技术， 2020（8）：151-155， 160. 10.13462/j.cnki.mmtamt.2020.08.037
	JING W W， ZHANG L， TIAN J. Multi-objective flexible job-shop scheduling problem researching based on adaptive NSGA-Ⅱ［J］. Modular Machine Tool and Automatic Manufacturing Technique， 2020（8）：151-155， 160. 10.13462/j.cnki.mmtamt.2020.08.037
23	辜勇，李雨，陈句，等. 多式联运碳减排研究综述［J］. 物流技术， 2021， 40（9）：1-5. 10.3969/j.issn.1005-152X.2021.09.001
	GU Y， LI Y， CHEN J， et al. Summary of researches on carbon emissions reduction in multimodal transport［J］. Logistics Technology， 2021， 40（9）：1-5. 10.3969/j.issn.1005-152X.2021.09.001

[1]	SUN Junyan, CHEN Zhirui, NIU Yaru, ZHANG Yuanyuan, HAN Fang. Joint optimization of picking operation based on nested genetic algorithm [J]. Journal of Computer Applications, 2020, 40(12): 3687-3694.
[2]	QIU Jigang, LI Wenlong, YANG Jia. Path optimization algorithm for team navigation based on multiple point collaboration [J]. Journal of Computer Applications, 2015, 35(7): 2093-2095.
[3]	LI Xun CHEN Ming. Idle travel optimization of tool path on intensive multi-profile patterns [J]. Journal of Computer Applications, 2014, 34(1): 281-285.
[4]	LAIZhizhu. Harmony search algorithm for solving selection of multimodal transportation scheme with several time windows [J]. Journal of Computer Applications, 2013, 33(09): 2640-2642.
[5]	HUANG Yangyu HU Wei YUAN Guodong. Global path planning based reciprocal velocity obstacles method for crowd evacuation [J]. Journal of Computer Applications, 2013, 33(06): 1753-1758.
[6]	GAO Man LIU Yi-an ZHANG Qiang. Application of improved ant colony algorithm to route planning of anti-ship missile [J]. Journal of Computer Applications, 2012, 32(09): 2530-2533.
[7]	Xiao-chong LIU Min DAI Gang ZHENG Qing-jun HUANG. Vehicle Route Planning Study for Cash Transport Van [J]. Journal of Computer Applications, 2011, 31(04): 1121-1124.
[8]	Yong-hong LUO Te-Fang CHEN You-Sheng ZHANG. Study on architecture of seamless transportation information grid [J]. Journal of Computer Applications, 2008, 28(11): 2749-2752.