Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (8): 1495-1504    DOI: 10.3785/j.issn.1008-973X.2023.08.003
    
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
Download: HTML     PDF(1116KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 27 November 2022      Published: 31 August 2023
CLC:  U 9  
  TP 182  
Fund:  长安大学中央高校基本科研业务费专项资助项目(300102220302, 300102222105); 陕西省科技计划资助项目(2023-JC-QN-0526)
Corresponding Authors: Nan DING     E-mail: limanman@chd.edu.cn;nanding@chd.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Man-man LI
Jia-hui SUN
Nan DING
Jing-shuai YANG
Cite this article:

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.

URL:

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


考虑服务定价的选择性众包配送优化

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


关键词： 物流工程,  配送路径,  非线性规划,  众包服务定价,  自适应大邻域搜索算法 
Fig.1 Selective crowdsourcing distribution routes considering service pricing
Fig.2 Hamilton circuit
Fig.3 Flowchart of adaptive large neighborhood search algorithm
Fig.4 Diagram of customer adding cost of distribution route most
Fig.5 Diagram of deleting continuous customers
$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
Tab.1 Distribution route of c101_10 case
Fig.6 Full crowdsourcing distribution mode
案例编号 无众包配送模式 选择性众包配送模式 全众包配送模式
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
Tab.2 Distribution cost of three crowdsourcing distribution modes
案例编号 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
Tab.3 Performance analysis of adaptive large neighborhood search algorithm
案例 ${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
Tab.4 Effect of crowdsourcing supply price sensitivity level on distribution scheme
$\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
Tab.5 Effect of number of transfer points on distribution scheme
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
Tab.6 Effect of time window width on distribution scheme
[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] Jing-shuai YANG,Yu-e YANG,Man-man LI,Yuan-yuan LI. Joint optimization of terminal distribution service mode and distribution routing[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(5): 900-910.
[2] Bao-feng SUN,Yue YANG,Jun-yan SHI,Li-li ZHENG. Dynamic pick-up and delivery problem considering dynamic events in real-world environment[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(8): 1604-1612.
[3] ZHOU Bing-hai, PENG Tao. Part-supply scheduling of automobile assembly line with hybrid teaching-learning-based optimization algorithm[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(10): 1854-1863.