团论文网
团论文网
-
【摘要】新零售的发展以及消费需求的多样化、定制化,衍生出大量复杂的城市物流配送需求。因此,对新环境下的两级车辆路径问题进行研究显得尤为必要。文中首先研究由配送中心－前置仓－需求点的两级车辆配送网络,考虑车辆固定成本、行驶成本、货物损耗成本、制冷成本等多个方面,同时兼顾顾客满意度和员工满意度,建立以总成本最低为目标的数学模型。然后,通过混合遗传算法,结合遗传算子和局部搜索策略,有效地搜索解空间,并找到一个满足多个成本约束的最优解。最后,结合标准算例进行分析。
【关键词】两级车辆路径;顾客满意度;员工满意度;混合遗传算法
两级车辆路径规划问题(Ｔｗｏ－ｅｃｈｅｌｏｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇ
Ｐｒｏｂｌｅｍ,２ＥＶＲＰ)涉及两个不同层级上车辆路径方案之间的协同,其核心在于同时考虑两个层级的车辆路径规划。Ｐｅｒｂｏｌｉ等[１]首次提出两级车辆路径规划问题的数学模型,并建立了２ＥＶＲＰ的标准算例,包含４组不同规模的算例集。在应用场景的选择上,Ｅｓｍａｉｌｉ,Ｓａｈｒａｅｉａｎ[２]研究了易腐产品的两级路径规划问题,并建立了考虑顾客等待时间最少和总配送成本最小的双目标模型。张汉鹏等[３]以应急物流为问题场景,考虑次生灾害的因素,构建了最大最小两级车辆路径规划模型,并以最小化最后完成救援物资配送的时间为目标函数进行求解。Ｌｉｕ等[４]为在线零售两级配送网络建立了非线性目标函数,该函数以优化总交通及碳排放费用为目标。Ｋａｎｃｈａｒｌａ,Ｒａｍａｄｕｒａｉ[５]假设每种配送的商品都由特定的仓库进行配送,即车场和货物之间存在着某种对应关系,同时由之前研究的单车场问题转变为多车场问题,之后Ｋｅｒｇｏｓｉｅｎ等[６]在研究中假设每个客户可以从多个仓库中请求多种商品。在Ｗａｎｇ等[７]的相关文献中有一个特殊案例,作者将每个客户与硬性和软性时间窗口相关联,虽然硬时间窗口定义了绝对最早和最晚的服务时间,但硬时间窗口内的软时间窗口定义了首选的服务时间。在求解算法上,作为首次建立２Ｅ－ＣＶＲＰ数学模型的文献[８],使用了分支定界法进行精确求解。Ｓａｎｔｏｓ等[９]在分支定界法的基础之上,增设了几类有效不等式,获得若干新标准算例的最优解及上限解。Ｂｒｅｕｎｉｇ等[１０]重建了２Ｅ－ＶＲＰ的数学模型,并将其解耦为多个有约束条件的多配送中心车辆路径规划问题,同样使用分支定界法来解决这个问题。邓丽君[１１]研究了基于顾客满意度的物流配送车辆调度优化问题,设计顾客满意度的模糊隶属度函数,并建立以顾客满意度和运输总成本为目标的优化模型。户佐安等[１２]用物流配送时间和货物完好性作为衡量顾客满意度的标准,给出了时间满意度函数和货物完好性满意度函数,建立多目标优化模型并用软件求解。现如今,学者对于顾客满意度的研究较多,但都忽略了员工满意度,因此本文综合考虑顾客满意度和员工满意度来对两级车辆路径优化进行研究。
１问题与模型
１.１两级车辆路径问题描述
本文将２Ｅ－ＶＲＰ问题定义为一个有向的完整图Ｇ＝(Ｎ,Ａ),Ｎ为节点集,Ａ为弧集。其中,Ｎ集合包含配送中心Ｄ、前置仓Ｓ和需求点Ｚ,Ａ包含配送中心和前置仓之间的弧线、前置仓和前置仓之间的弧线、前置仓和需求点之间的弧线以及需求点和需求点之间的弧线。当车辆在弧ｉｊ上行驶时会产生运输成本Ｃｉｊ,该成本与节点ｉ和节点ｊ之间的距离ｄｉｊ有关。
本文考虑的是软时间窗,即车辆可以在时间窗外为需求点提供服务,但是会产生相应的惩罚成本。２Ｅ－ＶＲＰ包括两个阶段,在第一阶段中,一级车辆从配送中心出发,将货物运至前置仓.在第二阶段中,二级车辆从各前置仓出发,将货物送给各需求点,最后再返回至前置仓。图１为２Ｅ－ＶＲＰ的一种可行的解决方案,包括１个配送中心、３个前置仓和１５个需求点。
为方便研究和分析,本文作出以下假设:
①前置仓位置已知,需求点的位置和需求量已知,各级车辆的固定成本已知.
②车辆在行驶过程中按照设定的数值匀速行驶.
③客户的最大的需求量不能大于车的容量.
④客户的时间窗已知且固定.
⑤所有配送车辆完成配送任务之后必须返回到起始节点。
１.２符号说明
Ｄ:配送中心,Ｄ＝{０}.
Ｓ:前置仓集合,Ｓ＝{１,２,…,ｓ}.Ｃ:需求点集合,Ｃ＝{１,２,…,ｎ}.
Ｂ:一级运输车辆集合(配送中心到前置仓),Ｂ＝(１,２,…,ｂ).
Ｋ:二级运输车辆集合(前置仓到客户),Ｋ＝{１,２,…,ｋ}.ＱＢ:一级同质运输车辆的额定装载量.
ＱＫ:二级同质运输车辆的额定装载量.ＤＢ:一级运输车辆的固定使用成本.
ＤＫ:二级运输车辆的固定使用成本.
ｃ１,ｃ２:一、二级车辆的单位行驶距离成本.[ＥＴｉ,ＬＴｉ]:客户ｉ的期望时间窗.
ｘｉｊｂ:０－１变量,若一级网络中车辆ｂ由节点ｉ行驶到节点
ｊ,则为１,否则为０.
ｙｉｊｋ:０－１变量,若二级网络中车辆ｋ由节点ｉ行驶到节点
ｊ,则为１,否则为０.
ｙｉｋ:０－１变量,若二级网络中节点ｉ由车辆ｋ进行配送,
则为１,否则为０。
１.３顾客满意度和员工满意度
对冷链物流而言,顾客满意与否主要和配送的时间有关[１３]。本文中客户的时间窗为软时间窗,即客户设定一个时间窗[ＥＴｉ,ＬＴｉ],其中ＥＴｉ为能接受配送车辆最早到达的时间,ＬＴｉ表示能接受配送车辆最晚到达的时间,如果车辆早于ＥＴｉ到达客户,则需要等待,对于客户而言,车辆早到会占用资源因此会有一定的惩罚成本.若晚于ＬＴｉ到达则需要为违约交付罚金,也会产生惩罚成本。
在已有的关于满意度的研究中,通常只考虑客户的满意度,而忽视员工的满意度。该问题中员工主要指配送员,而配送员作为谋生型员工,其满意度主要取决于生理层次的满意度构成因素,即薪资和工作强度[１４]。
工作强度主要通过工作时间和工作饱和度进行刻画[１５]。企业设置的理论工作时间为Ｔ,配送员Ｋ实际工作时间为ＴＫ,当实际工作时间大于理论工作时间时,员工满意度会降低,当实际工作时间小于理论工作时间时,员工满意度会增加。工作饱和度是指配送员为了完成配送任务所花的时间与全天工作时间的比值。假设配送员Ｋ的全天工作时间为ＴＫ,其在配送过程中因为早于顾客能接受的最早到达时间而产生的等待时间总和为Ｂ,则工作饱和度计算公式如下:
工作强度表示如下:
配送员的薪资与配送货物的重量和距离有关,同时企业设置的理论配送客户点的数量为ｎ,当配送员配送数量大于ｎ时会有激励奖金。假设配送员Ｋ配送货物的每吨公里费为ｘ,Ｋ服务的客户用集合Ｙ＝{１,２,…,ｙ}表示,客户之间的距离用ｄｉｊ表示(ｉ,ｊ∈ｙ),Ｌ表示配送员驾驶车辆从客户ｉ到客户ｊ时的载重量,配送员的薪资满意度计算公式如下:
基于公平理论的思想,配送员满意度取决于所有配送员工作强度和工作薪酬是否均衡。本文取所有配送员的工作强度、工作薪酬满意度的离散系数刻画满意度的均衡性。假设二级配送网络中所有配送员的工作强度均值为λＫ,配送员工作强度均衡的计算公式为:
假设二级配送网络中所有配送员的薪资均值为μK,配送员薪资均衡的计算公式为:
1.4数学模型
本文的目标函数为整个运输网络的总成本最小,主要的成本包括车辆的固定成本、车辆的行驶成本、货物的损耗成本、车辆的制冷成本以及惩罚成本。
①一二级车辆运输过程中的固定成本(Z1)
配送车辆从起始点出发为需求点提供配送服务时会产生一定的固定费用,主要包括驾驶员的工资、车辆的折旧费、高速公路的过路费等。具体公式如式(6)所示。
Z1由一级运输网络的固定成本和二级网络的固定成本共同构成,与使用车辆的数量有关,使用的车辆越多,固定成本越大。
②一二级运输车辆的行驶成本(Z2)
③运输过程中产品的货损成本(Z3)
冷链配送选用冷藏车来使产品处于适宜的环境中,对产品的保护性较好,所以仅考虑生鲜本身和配送时间推移影响下的货损[15]。货损表达式如下:
式(8)表示车辆在配送过程中的货损成本;
式(9)表示车辆在卸货过程中的货损成本,其中q in表示车辆离开客户点i时车上剩余货物的重量,Ti表示车辆在客户点i的服务时间(如果车辆早到,Ti等于车辆等待时间加上ti)。
④违反时间窗和未满足配送员满意度的惩罚成本(Z4)
本文中客户的时间窗为软时间窗,即客户设定一个时间窗[ETi,LTi],其中ETi表示为能接受配送车辆最早到达的时间,LTi表示能接受配送车辆最晚到达的时间。如果车辆早于ETi到达客户,则需要等待从而产生等待成本;若晚于LTi到则需要为违约交付罚金,从而产生惩罚成本。二级配送网络中因为违反时间窗而产生的惩罚成本如式(11)所示 :
配送员满意度与工作强度、薪资的离散程度有关,离散程度越小代表分配越均匀,反之代表分配不均。对于配送员而言,分配不均会对其工作积极性产生影响,最后可能会导致配送效率的降低;对于企业而言,分配不均会导致资源的浪费,出现前置仓服务的需求点数量差异大、车辆与车辆之间服务的需求点数量不均等现象。因此,需要设置一个最低的标准,若优化方案的离散值大于该值需加上一定的惩罚成本。具体计算公式如(12)式所示。
其中,M1表示配送员工作强度的离散系数,M2表示配送员工作强度的离散系数,Δ表示惩罚系数。基于以上描述,本文建立以总成本最小为目标函数的数学模型。目标函数如(13)式所示。
约束条件式(14)确保从配送中心送出的货物总量等于所有服务点需求量总和;式(15)确保从配送中心出发的一级配送车辆满足容量约束;式(16)确保每个前置仓最多只能被一辆车服务一次;式(17)确保一级配送网络中为前置仓服务的车和从该前置仓离开的车为同一辆;式(18)确保从各前置仓出发的二级配送车辆满足容量约束;式(19)确保所有需求点都被二级配送车辆服务且仅服务一次;式(20)确保二级配送网络中为需求点服务的车和从该需求点离开的车为同一辆;式(21)确保前置仓之间没有车辆相互配送;式(22)消除子回路;式(23)确保一级配送网络的所有车辆都空车返回配送中心;式(24)确保二级配送网络的所有车辆都空车返回前置仓。
2混合遗传算法设计
2E-VRP问题属于NP难问题,包括两阶段配送网络:由配送中心送至各前置仓为一级配送网络,再由前置仓送至各需求点为二级配送网络。一级配送网络较为简单,可通过精确算法求解,二级配送网络复杂度较高,需要利用启发式算法进行求解,本文针对二级配送网络的求解思路如下:
Step1客户预分配。K-means聚类方法是一种常用的无监督学习算法,可以将数据集分成K个较为相似的组。将客户按照他们的位置坐标分成Ｋ个组,其中Ｋ是车场的数量。然后,将每个客户分配给最近的车场,以便将ＭＤＶＲＰ问题转化为求解Ｋ个ＣＶＲＰ问题。
Ｓｔｅｐ２利用遗传算法求解多个ＣＶＲＰ问题。遗传算法的具体步骤如下:
Ｓｔｅｐ２.１初始化种群:随机生成初始解,每个解表示一个可能的路径方案,也就是车辆应该访问客户的顺序,用一组从１到ｎ(ｎ表示预分配到该车场的客户数量)的不重复的正整数表示。
Ｓｔｅｐ２.２适应度评估:计算每个个体(路径方案)的适应度,以车辆行驶的总成本的倒数为计算值。
Ｓｔｅｐ２.３选择:根据个体的适应度进行选择,选择一些较优秀的个体作为父代,用于繁殖下一代。
Ｓｔｅｐ２.４交叉:对选定的父代进行交叉操作,产生新的个体(子代)。交叉操作模拟了生物界的基因重组过程.变异:对子代进行变异操作,以增加种群的多样性。变异操作模拟了生物界的基因突变过程.替换:用新生成的子代替换掉部分较差的个体,形成新一代种群。
Ｓｔｅｐ２.５重复迭代:重复执行Ｓｔｅｐ２.２至Ｓｔｅｐ２.４,直到达到停止条件(如达到最大迭代次数或找到满意的解)。
Ｓｔｅｐ２.６输出结果:从最终种群中选择适应度最高的个体作为最优解,即最优路径方案。
Ｓｔｅｐ３利用模拟退火算法对Ｋ个ＣＶＲＰ问题进行整合并再次优化求解出更优解。
２.１适应度函数
在遗传算法中,个体的适应度是衡量其优劣的指标,通常与目标函数相关。对于总成本最小化的问题,选择将目标函数的倒数作为适应度函数,能够更好地反映个体的优劣。因此,个体的适应度值越高,其性能就越优秀,这有助于遗传算法在种群中搜索到最优解。具体的表达式如式(２５)所示:
其中,Ｆ为适应度函数,Ｚ为总成本表达式。
２.２遗传算子选择
本文采用轮盘赌选择法。轮盘赌选择法是一种基于个体适应度值的选择方法,其原理是根据每个个体在种群中的适应度值计算其在子代中被选择的概率。该方法也称为适应度比例法。在轮盘赌选择中,个体的适应度ｆｉ占总适应度Ｆ的比例确定了个体在轮盘上的区域大小。通过随机转动轮盘,并根据指针最终停留的位置来选择个体。被选中的概率与个体的适应度占总适应度的比值成正比。指针最终停留的位置是由一个范围在０到１之间的随机数确定的。每个个体被选中的概率ｐｉ如式(２６)所示。
交叉:本文选择两点交叉作为遗传算法的交叉操作。在这种操作中,相互配对的两个染色体会随机选择两个交叉点,然后交换这两个点之间的基因片段,以生成新的个体。具体而言,该操作的步骤包括:①在两个相互配对的个体编码串中随机选择两个交叉点.②对这两个个体,在所选的交叉点之间交换基因片段。两条父代染色体通过对交叉部分进行基因互换之后,可能会存在重复基因,但是本文中每个数值代表一个需求点,是不允许存在重复项的,因此需要通过映射关系来消除重复项。
变异:对每一条可行的配送路线,除首尾节点之外,交换任意两点位置,生成新的解从而增加解的多样性,使遗传算法搜索的空间增大。
２.３模拟退火
利用遗传算法求解第二阶段的车辆路径规划问题的前提是对每个需求点进行预分配,即固定了每个需求点所属的配送中心,但路线也会随着配送中心的变化而变化,因此有可能会产生更优的解。将遗传算法求出的最优解作为ＳＡ算法的初始解,然后随机交换两个需求点所属的配送中心生成新的配送方案。
二级网络服务的终端为需求点,因此涉及的节点数量较多,往往会达到上百个,需要利用启发式算法进行求解,而一级网络涉及到的节点数量就少很多,通常只有数十个。在对二级网络进行规划之后,利用精确算法就可以求解出一级网络的配送路径,从而得到一个完整的两级车辆配送路径方案。
３算例分析
本文选用Ｓｅｔ２ａ＿Ｅ－ｎ２２－ｋ４－ｓ６－１７标准算例进行求解。该算例中有一个配送中心、２个前置仓、２１个需求点。具体数据如表１所示,其中编号０表示配送中心,编号２２和２３表示两个前置仓,编号１－２１表示需求点,一级车辆的最大装载量为１５０００,二级车辆的最大装载量为６０００。求解结果显示,一号卫星场使用了２辆车,二号卫星场使用了３辆车。具体安排如下:车辆１从１号卫星场出发→３→４→１１→１３→１０→８→６→１号卫星场,总装载量为５８００.车辆２从１号卫星场出发→１→２→５→７→９→１卫星场,总装载量为５２００.车辆３从２号卫星场出发→１８→１５→１２→１４→１６→２号卫星场,总装载量为５５００.车辆４从２号卫星场出发→２０→２１→１９→２号卫星场,总装载量为５０００.车辆５从２号卫星场出发→１７→２号卫星场,总装载量为１０００。具体的路线安排如图２所示。
3结语
综上所述,在研究时考虑顾客满意度量化为时间窗约束、将员工满意度量化为工作强度和薪资的离散程度,并且将其转换为惩罚成本添加到目标函数中,求总成本最低。考虑到二级配送网络为多车场问题,直接利用遗传算法进行初始解构造时随机性强,因此,先利用聚类分析法将各需求点分配到各前置仓,从而将多车场问题简化为若干个单车场问题。此时,再用遗传算法求解可以缩短搜索时间,最后用模拟退火算法对结果进行再次优化从而得出相对最优解。
[参考文献]
[1]Perboli G,Tadei R,Vigo D.The two-echelon capacitated[J].Transportation Science,2011,45(3):364-380-echelon capacitated vehicle routing problem for perishable products with the environmental factor[J].International Journal of Engineering,2017,30(4):523-531.
[3]张汉鹏,廖毅,邱菀华.基于情景分析的应急两级车辆路径问题研究[J].系统科学与数学,2016,36(06):759-769.
[4]Liu D,Deng Z,Mao X,et al.Two-Echelon vehicle-routingroblem:Optimization of autonomous delivery vehicle-assisted E-grocery distribution[J].IEEE Access,2020,8108705-108719.
[5]Kancharla,S.R.,Ramadurai,G.Multi-depot two-echelon
fuel minimizing routing problem with heterogeneous fleets:Model and heuristic[J].Networks and Spatial Economics,
[6]Kergosien,Y.,Lenté,C.,Billaut,J.-C.,Perrin,S.Metaheuristic algorithms for solving two interconnected vehicle routing problems in a hospital complex[J].Computers&Operations Research,2013,40(10):2508-2518.
[7]Wang,Y.,Li,Q.,Guan,X.,Xu,M.,Liu,Y.,Wang,H.Two-echelon collaborative multi-depot multi-period vehicle routing problem[J].Expert Systems with Applications,2021,167:114-201.
[8]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.-price algorithms for the two-echelon capacitated vehiclerouting problem[J].Optimization Letters,2013,7(7):1537-1547.
[10]Breunig,U.,Baldacci,R.,Hartl,R.F.,Vidal,T.Theelectric two-echelon vehicle routing problem[J].Computers&Operations Research,2019,103:198-210.
[11]邓丽君.基于客户满意度的物流配送车辆调度优化模型与算法研究[D].北京:北京交通大学,2012.
[12]户佐安,贾叶子,李博威,等.考虑顾客满意度的车辆路径优化研究[J].工业工程,2019,22(1):100-107.
[13]张树柱,邱兵兵,山家骏,等.考虑驾驶员疲劳的车辆路径优化及算法研究[J].工业工程,2023,26(02):132-140+184.
[14]马成颖,牟海波.考虑路况、配送员与顾客满意度的冷链物流车辆配送路径优化方法[J].交通信息与安全,2022,40(05):156-168.
[15]方文婷,艾时钟,王晴,等.基于混合蚁群算法的冷链物流配送路径优化研究[J].中国管理科学,2019,27(11):107-115.
[16]胡蓉,陈文博,钱斌,等.学习型蚁群算法求解绿色多车场车辆路径问题[J].系统仿真学报,2021,33(09):2095-2108.后台-系统设置-扩展变量-手机广告位-内容正文底部 -
本文标签：
考虑顾客和员工满意度的两级车辆路径优化研究论文
人参与 2025-05-07 11:27:14 分类 : 管理学 点这评论 作者：团论文网 来源：https://www.tuanlunwen.com/
-
站内搜索
-
随机文章
-
标签列表
-
-
最近发表
-
-
热门文章 | 最新文章 | 随机文章
-
-
最新留言
-
首页 论文知识 教育论文 毕业论文 教学论文 经济学 管理学 职称论文 法学 理学 医学 社会学 物理学 文献 工程论文 学位论文 研究论文
Powered 团论文网 版权所有 备案号：鄂ICP备2022005557号统计代码
全站搜索