Please wait a minute...
浙江大学学报(工学版)  2023, Vol. 57 Issue (8): 1495-1504    DOI: 10.3785/j.issn.1008-973X.2023.08.003
计算机技术     
考虑服务定价的选择性众包配送优化
李嫚嫚1(),孙加辉2,丁楠1,*(),杨京帅1
1. 长安大学 汽车学院,陕西 西安 710061
2. 西安航天动力试验技术研究所,陕西 西安 710100
Selective crowdsourcing distribution optimization considering service pricing
Man-man LI1(),Jia-hui SUN2,Nan DING1,*(),Jing-shuai YANG1
1. School of Automobile, Chang’an University, Xi’an 710061, China
2. Xi’an Aerospace Propulsion Test Technique Institute, Xi’an 710100, China
 全文: PDF(1116 KB)   HTML
摘要:

提出众包服务定价与选择性众包配送方案联合优化方法. 根据众包服务价格与众包供给量关系,构建众包供给-价格函数,进而构建出优化众包服务价格、客户分配方案以及配送路径的混合整数非线性规划模型,并采用大M法将其处理成混合整数线性规划模型. 依据问题领域知识设计局部搜索规则,并结合节约算法、禁忌搜索算法和模拟退火算法设计出求解大规模案例的自适应大邻域搜索算法. 自适应大邻域搜索算法的性能优于GUROBI、最早配送规则以及节约算法;选择性众包配送服务模式在降低配送成本上优于无众包配送服务模式和全众包配送模式;众包配送服务模式适用于众包供给价格敏感度高、客户服务时间窗紧的场景;适当增加中转点或者拓宽客户服务时间窗可以降低配送成本.

关键词: 物流工程配送路径非线性规划众包服务定价自适应大邻域搜索算法    
Abstract:

A method was proposed to jointly optimize crowdsourcing service price and selective crowdsourcing distribution scheme. A crowdsourcing supply function about price was firstly constructed based on their relationship and then a mix-integer non-linear programming model was constructed to optimize the crowdsourcing service price, customer assignment scheme and distribution routes. The mix-integer non-linear programming model was further transformed into a more easily solved mix-integer linear programming model using the big-M method. To solve large-scale cases, an adaptive large neighborhood search algorithm was designed, combined with the problem domain knowledge-based local searches, saving algorithm, tabus search algorithm and simulated annealing algorithm. The performance of the adaptive large neighborhood search algorithm is superior to that of GUROBI solver, the earliest ready time rule and the saving algorithm. Numerical analyses show that the selective crowdsourcing distribution mode is better than no crowdsourcing distribution mode and full crowdsourcing distribution mode in lowering the distribution cost, the crowdsourcing distribution service mode is suitable for the scenarios with the high crowdsourcing supply service price sensitivity level and tight time window, and the distribution cost can be reduced by reasonably adding transfer points and widening time windows.

Key words: logistics engineering    distribution route    non-linear programming    crowdsourcing service pricing    adaptive large neighborhood search algorithm
收稿日期: 2022-11-27 出版日期: 2023-08-31
CLC:  U 9  
基金资助: 长安大学中央高校基本科研业务费专项资助项目(300102220302, 300102222105); 陕西省科技计划资助项目(2023-JC-QN-0526)
通讯作者: 丁楠     E-mail: limanman@chd.edu.cn;nanding@chd.edu.cn
作者简介: 李嫚嫚(1991— ),女,讲师,从事交通运输系统建模与优化研究. orcid.org/0000-0002-6906-3240. E-mail: limanman@chd.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
李嫚嫚
孙加辉
丁楠
杨京帅

引用本文:

李嫚嫚,孙加辉,丁楠,杨京帅. 考虑服务定价的选择性众包配送优化[J]. 浙江大学学报(工学版), 2023, 57(8): 1495-1504.

Man-man LI,Jia-hui SUN,Nan DING,Jing-shuai YANG. Selective crowdsourcing distribution optimization considering service pricing. Journal of ZheJiang University (Engineering Science), 2023, 57(8): 1495-1504.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.08.003        https://www.zjujournals.com/eng/CN/Y2023/V57/I8/1495

图 1  考虑服务定价的选择性众包配送路径
图 2  哈密尔顿回路
图 3  自适应大邻域搜索算法流程
图 4  导致配送成本增加最多的客户示意图
图 5  连续客户删除示意图
$R$ $\left[ {{S_i},{L_i}} \right]$/min ${a_i}$/min ${q_i}$/kg ${g_i}$/kg ${Q_{\text{e}}}$/kg
0 [0, 1 236] 0 0 150 200
5 [15, 375] 15 10 140 200
3 [16, 376] 106 10 130 200
7 [18, 378] 198 20 110 200
10 [204, 564] 293 10 100 200
8 [110, 470] 387 20 80 200
9 [390, 750] 479 10 70 200
6 [482, 842] 571 20 50 200
4 [575, 935] 663 10 40 200
2 [668, 1 028] 760 30 10 200
1 [760, 1 120] 863 10 0 200
0 [0, 1 236] 972 0 0 200
表 1  c101_10案例的配送路径
图 6  全众包配送模式
案例编号 无众包配送模式 选择性众包配送模式 全众包配送模式
TC/元 VC/元 CC/元 AP/(元·单?1) CN TC/元 VC/元 CC/元 AP/(元·单?1) CN TC/元 VC/元 CC/元 AP/(元·单?1) CN
c101_10 147.50 147.50 0 0 0 147.50 147.50 0 0 0 167.92 155.92 12 4 3
c102_10 147.25 147.25 0 0 0 147.25 147.25 0 0 0 157.73 145.73 12 4 3
c103_10 147.25 147.25 0 0 0 147.25 147.25 0 0 0 157.73 145.73 12 4 3
c105_10 148.33 148.33 0 0 0 148.33 148.33 0 0 0 168.75 156.75 12 4 3
r101_10 629.53 629.53 0 0 0 629.53 629.53 0 0 0 629.55 627.55 2 2 1
r105_10 523.07 523.07 0 0 0 521.97 519.97 2 2 1 521.97 519.97 2 2 1
rc101_10 365.91 365.91 0 0 0 363.57 361.57 2 2 1 372.18 368.18 4 2 2
rc102_10 349.68 349.68 0 0 0 348.05 346.05 2 2 1 356.66 352.66 4 2 2
rc103_10 349.68 349.68 0 0 0 348.05 346.05 2 2 1 356.66 352.66 4 2 2
rc105_10 359.31 359.31 0 0 0 350.17 348.17 2 2 1 358.78 354.78 4 2 2
表 2  3种众包配送模式的配送成本
案例编号 GUROBI E-R-T-R S-A ALNS
TC/元 CT/s TC/元 CT/s GAP% TC/元 CT/s GAP% TC/元 CT/s GAP%
1)注:黑粗体表示ALNS获得的解质量不劣于2 h求解时间限制下GUROBI 9.1获得的解质量.
c101_10 147.50 22.22 161.57 0.03 9.54 267.54 0.06 81.39 147.501) 0.41 0.00
c102_10 147.25 1 005.46 282.73 0.03 92.00 272.62 0.04 85.14 147.25 0.53 0.00
c103_10 147.25 1 035.00 282.73 0.03 92.00 272.62 0.04 85.14 147.25 0.56 0.00
c104_10 146.41 7 200.00 161.19 0.03 10.10 147.66 0.06 0.86 146.41 0.69 0.00
c105_10 148.33 1.56 161.57 0.04 8.93 267.18 0.14 80.13 148.33 18.62 0.00
r101_10 629.53 95.02 653.85 0.03 3.86 742.35 0.05 17.92 629.53 0.46 0.00
r102_10 499.77 7 200.09 709.34 0.03 41.93 624.16 0.05 24.89 503.92 0.34 0.83
r103_10 499.77 7 200.09 709.34 0.03 41.93 624.16 0.04 24.89 503.92 0.34 0.83
r104_10 378.21 7 200.06 620.43 0.03 64.04 492.57 0.06 30.24 378.21 0.51 0.00
r105_10 521.97 46.79 523.09 0.05 0.21 626.85 0.04 20.09 521.97 0.53 0.00
rc101_10 363.57 6.42 452.58 0.26 24.48 670.87 0.05 84.52 363.57 0.45 0.00
rc102_10 348.05 4 302.53 568.80 0.04 63.42 511.06 0.05 46.84 348.05 0.90 0.00
rc103_10 348.05 4 103.36 568.80 0.03 63.42 511.06 0.05 46.84 348.05 0.94 0.00
c101_100 1 852.66 7 200.00 3 249.91 0.37 75.42 1 893.39 2.32 2.20 1 727.40 6.23 ?6.76
c102_100 1 727.40 7 200.00 3 588.87 0.38 107.76 2 296.24 2.18 32.93 1 727.40 4.51 0.00
c103_100 1 731.75 7 200.00 4 392.15 0.52 153.63 2 206.12 2.23 27.39 1 727.32 5.09 ?0.26
c104_100 1 750.42 7 200.00 4 570.76 0.41 161.12 1 917.40 3.14 9.54 1 725.21 4.00 ?1.44
c105_100 1 727.40 7 200.00 4 188.41 0.38 142.47 2 013.64 2.36 16.57 1 727.40 5.38 0.00
r101_100 3 296.94 7 200.00 4 567.15 0.50 38.53 4 802.14 3.32 45.65 3 362.78 17.17 2.00
r102_100 2 985.31 7 200.00 4 792.02 0.53 60.52 4 133.31 2.53 38.45 2 989.25 17.61 0.13
r103_100 2 627.45 7 200.00 5 381.12 0.60 104.80 3 365.45 2.27 28.09 2 478.48 5.33 ?5.67
r104_100 2 291.19 7 200.00 5 400.40 0.76 135.70 2 403.18 2.28 4.89 1 867.78 21.59 ?18.48
r105_100 2 628.43 7 200.00 5 780.48 0.61 119.92 3 635.05 2.27 38.30 2 530.38 16.01 ?3.73
rc101_100 2 955.63 7 200.00 4 395.52 0.47 48.72 4 345.50 2.37 47.02 3 067.33 15.75 3.78
rc102_100 2 744.13 7 200.00 4 679.20 0.53 70.52 3 894.32 2.37 41.91 2 756.06 8.80 0.43
rc103_100 2 648.47 7 200.00 5 000.11 0.60 88.79 3 243.46 2.20 22.47 2 507.22 22.56 ?5.33
rc104_100 2 386.94 7 200.00 4 521.67 0.51 89.43 2 590.27 2.45 8.52 2 125.90 5.65 ?10.94
rc105_100 2 983.89 7 200.00 4 095.16 0.47 37.24 3 691.45 2.26 23.71 2 734.31 18.66 ?8.36
表 3  自适应大邻域搜索算法性能分析
案例 ${E_m}$/
(人·元?1·单)
TC/元 VC/元 CC/元 AP/元 CN CM
c101_10 0.5 147.50 147.50 0.00 0.00 0 4
2.0 147.26 146.75 0.50 0.50 1 4
8.0 146.88 146.75 0.13 0.13 1 4
16.0 146.81 146.69 0.13 0.06 2 4
64.0 146.72 146.69 0.02 0.02 2 4
128.0 146.70 146.69 0.02 0.01 2 4
256.0 146.70 146.69 0.01 0.00 2 4
512.0 146.69 146.69 0.00 0.00 2 4
c101_100 0.5 1 706.24 1 682.24 24.00 2.00 12 80
2.0 1 676.15 1 634.65 41.50 1.43 29 80
8.0 1 519.56 1 490.94 28.63 0.58 49 80
16.0 1 504.58 1 490.46 14.13 0.28 50 80
64.0 1 504.42 1 500.42 4.00 0.07 54 80
128.0 1 493.10 1 491.04 2.06 0.04 54 80
256.0 1 489.46 1 488.30 1.15 0.02 56 80
512.0 1 481.98 1 481.25 0.72 0.01 56 80
表 4  众包供给价格敏感度对配送方案的影响
$\left| M \right|$ c101_10_1 c101_10_2 c101_100
TC/元 CM CN TC/元 CM CN TC/元 CM CN
1 147.50 4 0 147.50 9 0 1 728.94 12 0
2 147.50 4 0 147.50 9 0 1 722.82 20 3
3 147.50 4 0 143.72 10 2 1 722.48 31 6
4 147.50 4 0 143.25 10 4 1 717.10 40 6
5 147.50 4 0 143.25 10 4 1 711.63 53 8
6 147.50 4 0 142.42 10 5 1 707.50 62 10
7 147.50 4 0 142.42 10 5 1 706.24 72 10
8 147.50 4 0 142.42 10 5 1 706.24 80 12
表 5  中转点数量对配送方案的影响
PR1) c101_10 r105_10 c101_100
TC/元 VN CN TC/元 VN CN TC/元 VN CN
1)注:改变后时间窗为[最早可服务时刻×比例,最晚可服务时刻×比例].
0.7 158.73 1 1 637.19 3 2 1 962.80 11 15
0.8 148.33 1 0 534.84 3 1 1 787.61 10 15
0.9 147.50 1 0 521.97 3 1 1 718.14 10 13
1.0 147.50 1 0 521.97 3 1 1 706.24 10 12
1.1 147.50 1 0 521.97 3 1 1 703.61 10 13
1.2 147.50 1 0 440.11 2 1 1 703.74 10 12
1.3 147.50 1 0 440.11 2 1 1 704.16 10 11
表 6  时间窗宽度对配送方案的影响
1 孟秀丽, 吴一凡, 刘波. 考虑延误险的多期众包物流服务质量优化[EB/OL]. (2022-06-29). https://kns.cnki.net/kcms2/article/abstract?v=3uoqIhG8C45S0n9fL2suRadTyEVl2pW9UrhTDCdPD67s_kBxcpWeybRhM3Sh7olHcoA4OxqnnQe4i9rLNQNlapD42t1x0ESs&uniplatform=NZKPT.
2 刘春玲, 王俊峰, 黎继子, 等 众包模式下冷链物流配送模型的仿真和优化分析[J]. 计算机集成制造系统, 2019, 25 (10): 2666- 2675
LIU Chun-ling, WANG Jun-feng, LI Ji-zi, et al Simulation and optimization model of cold chain logistics delivery under crowdsourcing mode[J]. Computer Integrated Manufacturing Systems, 2019, 25 (10): 2666- 2675
3 WANG Y, ZHANG D, LIU Q, et al Towards enhancing the last-mile delivery: an effective crowd-tasking model with scalable solutions[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 93 (1): 279- 293
4 杜子超, 卢福强, 王素欣, 等 众包物流配送车辆调度模型及优化[J]. 东北大学学报: 自然科学版, 2021, 42 (8): 1210- 1216
DU Zi-chao, LU Fu-qiang, WANG Su-xin, et al Vehicle scheduling model and optimization of crowdsourcing logistics distribution[J]. Journal of Northeastern University: Natural Science, 2021, 42 (8): 1210- 1216
5 王文杰, 孙中苗, 徐琪 考虑社会配送供应能力的众包物流服务动态定价模型[J]. 管理学报, 2018, 15 (2): 293- 300
WANG Wen-jie, SUN Zhong-miao, XU Qi Dynamic pricing for crowdsourcing logistics services with socialized providers[J]. Chinese Journal of Management, 2018, 15 (2): 293- 300
6 王文杰, 孙中苗, 徐琪, 等 随机需求下考虑服务商竞争的众包物流动态定价策略[J]. 工业工程与管理, 2018, 23 (2): 114- 121
WANG Wen-jie, SUN Zhong-miao, XU Qi, et al Dynamic pricing for crowdsourcing logistics services with stochastic demand and competitive providers[J]. Industrial Engineering and Management, 2018, 23 (2): 114- 121
7 HUANG K, ARDIANSYAH M N A decision model for last-mile delivery planning with crowdsourcing integration[J]. Computers and Industrial Engineering, 2019, 135: 898- 912
doi: 10.1016/j.cie.2019.06.059
8 KAFLE N, ZOU B, LIN J Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery[J]. Transportation Research Part B: Methodological, 2017, 99 (1): 62- 82
9 王文杰, 陈颖, 蒋帅杰 考虑平台竞争的众包物流社会配送服务最优定价策略[J]. 运筹与管理, 2020, 29 (10): 11- 20
WANG Wen-jie, CHEN Ying, JIANG Shuai-jie Optimal pricing for crowdsourcing logistics socialized services under competitive platforms[J]. Operations Research and Management Science, 2020, 29 (10): 11- 20
10 BERTSIMAS D, TSITSIKLIS J N. Introduction to linear optimization [M]. Belmont: Athena Scientific, 1997.
11 伍国华, 毛妮, 徐彬杰, 等 基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J]. 控制与决策, 2023, 38 (1): 201- 210
WU Guo-hua, MAO Ni, XU Bin-jie, et al Research on the cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search[J]. Control and Decision, 2023, 38 (1): 201- 210
12 郭放, 黄志红, 黄卫来 考虑前置仓选址与服务策略的同时取送货车辆路径问题[J]. 系统工程理论与实践, 2021, 41 (4): 962- 978
GUO Fang, HUANG Zhi-hong, HUANG Wei-lai Integrated sustainable planning of fast-pick area network and vehicle routing problem with simultaneous delivery and pick-up[J]. System Engineering: Theory and Practice, 2021, 41 (4): 962- 978
13 刘明剑, 谭国珍, 魏欣, 等 基于禁忌搜索的交叉口自治车辆调度方法[J]. 中国公路学报, 2016, 29 (2): 123- 129
LIU Ming-jian, TAN Guo-zhen, WEI Xin, et al Autonomous vehicles scheduling method based on tabu search at intersection[J]. China Journal of Highway and Transport, 2016, 29 (2): 123- 129
[1] 杨京帅,杨玉娥,李嫚嫚,李园园. 末端配送服务模式与路径联合优化[J]. 浙江大学学报(工学版), 2023, 57(5): 900-910.
[2] 施德华,蔡英凤,汪少华,陈龙,朱镇,高立新. 系统效率最优的功率分流式混合动力汽车非线性预测控制[J]. 浙江大学学报(工学版), 2019, 53(12): 2271-2279.
[3] 周炳海, 彭涛. 基于混合教-学算法的汽车装配线物料供应调度[J]. 浙江大学学报(工学版), 2018, 52(10): 1854-1863.
[4] 孙跃, 赵志斌, 苏玉刚, 唐春森. 非接触电能传输系统参数非线性规划[J]. J4, 2013, 47(2): 353-360.
[5] 贺益君 陈德钊. 适于混合整数非线性规划的混合粒子群优化算法[J]. J4, 2008, 42(5): 747-751.
[6] 王丽军 张宏建 李希. 对二甲苯氧化反应器网络的合成[J]. J4, 2005, 39(9): 1413-1417.