基于快递业物流的优化调度问题研究

《基于快递业物流的优化调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于快递业物流的优化调度问题研究摘要：现代化物流分支广泛，本文针对现代化物流业中的快递业物流优化调度问题，建立了为使任务成本最小的优化模型，根据快递业物流特点，基于遗传算法利用其中。利用真实的用例来验证遗传算法在快递业物流调度中的可行性。关键词：快递业；优化模型；遗传算法0引言快递业作为现代物流业的一个分支，在电子商务市场的发展下，快递业物流也得到迅猛发展。车辆调度问题（VehicleschedulingProblem，简称VSP）作为物流业的核心问题，各个领域专家学者提出了不同的研究方案[1，2]。上个世纪中叶，Dant

2、zing和Ramser最早提出了商旅问题[3]，标志着VSP理论的正式成立。本文从物流业特点出发，从快递业物流配送物件相对较小，快递员（配送人员）能力限制，及客户点分散等的综合现状下分析，找到最优的调度方案。8VSP问题属于NP-hard问题，在规模较小的情况下可以使用精确算法求出最优解[4]，而启发算法则在较大的规模下有着非常重要的作用[5，6]。目前大量使用的智能算法有模拟退火算法、禁忌搜索算法、蚁群算法等智能优化算法，考虑到实际和本文的模型特点，采用遗传算法对问题进行求解。1问题描述和数学模型的确立快递业车辆调度问题

3、可描述为：有N个客户点，并且每个客户点的配送量及位置已知，快递员k从快递站点出发到达这批客户点。快递员在配送任务完成后，返回快递站点。在选择和确定实际配送路线和完成配送货任务过程中，使得总费用最小。用1，2，3，…，M表示快递员的编号，令m={1，2，3，…，M}；R表示m的行驶速度，设为一常值；设每个快递物件重量大小为1（由于快递物件重量相对较小）；Nmax表示为快递员在一次配送任务的最大工作量（件数）；eij表示客户点i与j之间所需的行驶成本（指距离，费用之和等）；设行驶单位距离成本为q，设q为1，eij与客户i到客户

4、j的行驶的距离dij成线性关系；p0表示快递员配送快递物件的每件提成，为固定值。设决策变量为：x■■=1快递员m从i离开后前往j0否则；模型描述为：min■■■e■+p■x■■（1）st.■■x■■=1，i=1，…，N，j≠i（2）■■x■■=1，j=1，…，N，i≠j（3）■x■■■x■■=1，m=1，…，M，i=0（4）■x■■≤N■，m=1，…，M，j=1，…，N（5）8e■=qd■=d■i，j=0，1，…，N（6）x■■∈0，1i，j=0，1，…，N，i≠j（7）式（1）表示目标函数，即最小任务成本。式（2）（3）

5、确保每个客户只能被一位快递员服务一次。式（4）确保所有的快递员都从快递站点出发且最终都返回快递站点。式（5）确保每次快递员的任务量不超过快递员的最大工作承受能力，即快递员容量限制为Nmax。式（6）i，j之间行驶成本计算说明。式（7）确保决策变量为0～1的决策变量。2模型求解快递业车辆调度问题：有N个客户点，并且每个客户点位置及配送量已知，有M个快递员，快递员从快递站点出发，配送完货物后回到快递站点，由于快递员最大工作能力限制，所以每次任务快递员配送货物有限。本文属于NP-hard问题，遗传算法[7]对上文模型求解具有良好

6、的特性。Malmborg[8]、BakerBarrie[9]等人在遗传算法应用于车辆调度问题进行了研究。本文也采用遗传算法对上述模型进行求解。具体内容如下：2.1染色体编码8染色体结构的设计对遗传算法是至关重要的，本文的染色体编码由三部分组成。第一部分是快递员编号，第二部分为客户点编号，第三部分为快递站点编号（设置为0）。例如本文中染色体的S结构可表示为：S：（1415202360）表示：编号为1的快递员从快递站点出发，经过的路径为客户点4→客户点1→客户点5→客户点2→快递站点0；编号为2的快递员从快递站点出发，经过的路

7、径为客户点3→客户点6→快递站点0。使用的快递员数为2个。2.2种群初始化初始种群包括多条染色体，每条染色体中客户点的顺序随机打乱，再根据快递员能力限制插入快递员编号。染色体长度是根据客户点是由使用的快递员数和客户点数决定的。2.3选择本文采用轮盘赌（roulettewheel）的方法，依照适应度函数值，从群里中找到比较适应环境的个体。2.4交叉根据适当的交叉率选择选择出需要交叉的种群，为了说明交叉过程，示例如下：任意选出两个父体1→4→1→5→2→0→2→3→6→01→3→2→5→1→0→2→6→4→0经过交叉，互换两个

8、基因段，去掉快递员编号和快递站点编号，得到两个子体为86→1→5→2→2→63→3→5→1→4→4按照这种交叉的操作方法，一条染色体中会出现相同的基因，那么就要把没有进行交换操作的基因段的重复基因与另外一条染色体按顺序进行交换，可得到6→1→5→3→2→42→3→5→1→4→6根据快递员能力约束，随机插