[go: up one dir, main page]

CN107506846B - 一种基于多目标粒子群优化算法的车辆调度方法与装置 - Google Patents

一种基于多目标粒子群优化算法的车辆调度方法与装置 Download PDF

Info

Publication number
CN107506846B
CN107506846B CN201710555113.1A CN201710555113A CN107506846B CN 107506846 B CN107506846 B CN 107506846B CN 201710555113 A CN201710555113 A CN 201710555113A CN 107506846 B CN107506846 B CN 107506846B
Authority
CN
China
Prior art keywords
vehicle
target
result
module
customer
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201710555113.1A
Other languages
English (en)
Other versions
CN107506846A (zh
Inventor
徐文星
王万红
边卫斌
王琴
何骞
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Beijing Institute of Petrochemical Technology
Original Assignee
Beijing Institute of Petrochemical Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Beijing Institute of Petrochemical Technology filed Critical Beijing Institute of Petrochemical Technology
Priority to CN201710555113.1A priority Critical patent/CN107506846B/zh
Publication of CN107506846A publication Critical patent/CN107506846A/zh
Application granted granted Critical
Publication of CN107506846B publication Critical patent/CN107506846B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/004—Artificial life, i.e. computing arrangements simulating life
    • G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/083—Shipping
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/10—Internal combustion engine [ICE] based vehicles
    • Y02T10/40—Engine management systems

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Physics & Mathematics (AREA)
  • Economics (AREA)
  • Human Resources & Organizations (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Strategic Management (AREA)
  • Development Economics (AREA)
  • General Business, Economics & Management (AREA)
  • Tourism & Hospitality (AREA)
  • Quality & Reliability (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Entrepreneurship & Innovation (AREA)
  • General Engineering & Computer Science (AREA)
  • Game Theory and Decision Science (AREA)
  • Biomedical Technology (AREA)
  • Artificial Intelligence (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Mathematical Physics (AREA)
  • Health & Medical Sciences (AREA)
  • Software Systems (AREA)
  • Biophysics (AREA)
  • Computational Linguistics (AREA)
  • Computing Systems (AREA)
  • Molecular Biology (AREA)
  • General Health & Medical Sciences (AREA)
  • Evolutionary Computation (AREA)
  • Data Mining & Analysis (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开了一种基于多目标粒子群优化算法的车辆调度方法与装置，用于解决以客户等待时间和送货车辆成本为优化目标的车辆调度问题，该车辆调度方法包括：一种构建车辆成本与客户等待时间的双目标优化模型；对每个目标粒子进行编码并得到编码结果；基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度。采本发明的技术方案，通过对粒子群算法进行改进，应用于物流中心的车辆调度，帮助物流中心节省车辆成本，减少客户等待的时间，给客户更好的用户体验。

Description

一种基于多目标粒子群优化算法的车辆调度方法与装置
技术领域
本发明涉及物流领域，尤其涉及一种基于多目标粒子群优化算法的车辆调度方法与装置。
背景技术
随着电子商务行业的发展，物流业已经成为了人们生活中非常重要的一个环节，在整个物流配送货物的过程中，有两个关键点。第一点是车辆装载问题(Vehicle FillingProblem，VFP)，也就是研究在货物装载的过程中使用什么装配方式能够相对节省时间并节省人力物力；另一个关键点是车辆路径问题(Vehicle Routing Problem，VRP)，就是研究车辆配送环节中，哪一辆车送哪几个货物点能够达到效率最大化的问题。车辆路径问题又可以分为两部分，一种是根据路径的空间特性，譬如考虑运输成本最低的问题，称为车辆路径问题，另外一种是考虑时间特性的情况下，在有限的时间或规定的时间范围内求解车辆路径优化问题的，称为车辆调度问题。
因此，目前亟需一种解决方案，以送货车辆运输成本与客户等待时间双优化目标问题的解决方案。
发明内容
本发明的主要目的在于公开一种基于多目标粒子群优化算法的车辆调度方法与装置，用于提出一种以送货车辆运输成本与客户等待时间双优化目标问题的解决方案。
为达上述目的，根据本发明的一个方面，公开一种基于多目标粒子群优化算法的车辆调度方法，并采用如下技术方案:
一种基于多目标粒子群优化算法的车辆调度方法包括：构建车辆成本与客户等待时间的双目标优化模型；对每个目标粒子进行编码并得到编码结果；基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度。
进一步地，所述构建车辆成本与客户等待时间的双目标优化模型包括：设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure BDA0001345512520000021
Figure BDA0001345512520000022
Figure BDA0001345512520000023
Figure BDA0001345512520000024
Figure BDA0001345512520000025
Figure BDA0001345512520000026
Figure BDA0001345512520000027
D0j＝D0i+Dij (5-8)
Figure BDA0001345512520000028
Figure BDA0001345512520000029
Figure BDA00013455125200000210
其中，
Figure BDA0001345512520000031
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
进一步地，所述对每个目标粒子进行编码并得到编码结果包括：设有M个客户点，表示为：1、2、3…M，K辆车进行配送；第一行用x1表示车辆的序号；第二行x2表示车辆运送客户点的顺序；所述编码结果为所述第一行与所述第二行组成的实数矩阵。
进一步地，所述根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作包括：将所述计算结果填入所述实数矩阵中；对x1进行取整操作后，得到每辆车对应的客户点；列出K辆车分别对应的客户点，得到每辆车的行驶路径。
进一步地，所述对所述寻优结果进行解码操作包括：将所述实数矩阵转化为一行数列；将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
根据本发明的另外一个方面，提供一种基于多目标粒子群优化算法的车辆调度装置，并采用如下技术方案：
一种基于多目标粒子群优化算法的车辆调度装置包括：构建模块，用于构建车辆成本与客户等待时间的双目标优化模型；编码模块，用于对每个目标粒子进行编码并得到编码结果；计算模块，用于基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；寻优模块，用于根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；解码模块，用于对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度。
进一步地，所述构建模块还用于：设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure BDA0001345512520000032
Figure BDA0001345512520000041
Figure BDA0001345512520000042
Figure BDA0001345512520000043
Figure BDA0001345512520000044
Figure BDA0001345512520000045
Figure BDA0001345512520000046
D0j＝D0i+Dij (5-8)
Figure BDA0001345512520000047
Figure BDA0001345512520000048
Figure BDA0001345512520000049
其中，
Figure BDA00013455125200000410
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
进一步地，所述编码模块还用于：设有M个客户点，表示为：1、2、3…M，K辆车进行配送；第一行用x1表示车辆的序号；第二行x2表示车辆运送客户点的顺序；所述编码结果为所述第一行与所述第二行组成的实数矩阵。
进一步地，所述寻优模块包括：填入模块，用于将所述计算结果填入所述实数矩阵中；取整模块，用于对x1进行取整操作后，得到每辆车对应的客户点；列出模块，用于列出K辆车分别对应的客户点，得到每辆车的行驶路径。
进一步地，所述解码模块包括：转化模块，用于将所述实数矩阵转化为一行数列；排列模块，用于将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
本发明通过对粒子群算法的改进，将多目标粒子群优化算法应用于物流中心的车辆调度问题，以客户等待时间和送货车辆运输成本为优化目标，将实际问题转化为多目标优化问题，进而帮助物流中心节省车辆成本，并给客户更好的用户体验。
附图说明
为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明中记载的一些实施例，对于本领域普通技术人员来讲，还可以根据这些附图获得其他的附图。
图1为本发明实施例所述的物流中心车辆运输图；
图2为本发明实施例所述的一种基于多目标粒子群优化算法的车辆调度方法的流程图；
图3为本发明实施例所述多样性指标示意图；
图4为本发明实施例所述的车辆调度装置的结构示意图。
具体实施方式
以下结合附图对本发明的实施例进行详细说明，但是本发明可以由权利要求限定和覆盖的多种不同方式实施。
粒子群算法依据生物仿生学对鸟类觅食行为的研究，种群通过对自己搜索路线的记忆和种群中的信息共享，具备较强的全局搜索能力。但同样这样的特点也会导致种群扎堆，指导粒子对种群过强的指导特性会让种群缺失一定的多样性，甚至是带领整个种群陷入局部最优点。
本申请针对现有基于粒子群算法的不足做了改进,并具体应用到物流中心的车辆调度问题上。
针对粒子群算法多样性方面的不足提出了IMOPSO算法，通过设计外部档案维护策略，在存储非劣解的过程中，保证了非劣粒子的多样性，同时能够对粒子的性能在不同的时期做出准确的判断，使表现性能更好的粒子成为指导粒子来引领种群的收敛。经过测试函数和其他算法之间的测试比较，证实了IMOPSO算法能够在维持算法多样性的同时，不会造成更高的算法复杂度，从而影响到粒子的收敛速度。
针对粒子群算法在求解复杂优化问题，尤其是多峰函数的时候，难以跳出局部最优值，局部搜索能力不强这一特点，结合模式搜索思想和高斯变异算子的思想和粒子群算法有效的协调计算，既保证了粒子群算法的全局搜索能力，也克服了局部搜索能力不强这一弱点，经过对benchmark的测试以及和其他算法的对比，证实了算法的可行性，同时和IMOPSO算法比较，讨论了加入局部搜索算法后，对粒子群算法性能究竟产生了怎样的影响以及如何去协调两个算法融合的问题。
本发明对于问题的解决采用了如下方案：
图1为本发明实施例所述的一种基于多目标粒子群优化算法的车辆调度方法的流程图。
参见图1所示，一种基于多目标粒子群优化算法的车辆调度方法包括：
S101：构建车辆成本与客户等待时间的双目标优化模型；
S103：对每个目标粒子进行编码并得到编码结果；
S105：基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；
S107：根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；
S109：对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度。
首先，粒子群算法具备很强的全局搜索能力，在处理局部极值点较多的优化目标的时候，容易陷入局部最优点。这是因为粒子在目标空间内搜索可行解的时候，种群是依赖群体得到的最优值来更新自己的速度从而到达新的位置的，如同鸟群一样，如果发现了类似食物的地点，通过个体记忆和群体内的信息共享机制，整个鸟群都会朝向有食物的地方飞行，如果那个地方并不是食物，只是类似食物的东西的时候，整个搜索过程就是失败的，但是整个鸟群都已经飞过来了。粒子群算法同样存在这样的局限性。
因此，步骤S101中，基于车辆成本与客户等待时间的双目标，构建算法更优的计算模型。
模式搜索算法的局部搜索能力较强，同时算法本身不依赖于对目标函数求解梯度的过程，算法就具备较广的应用领域。而高斯因子因为其操作简便，具备很强的灵活性同样具备很强的优势。
模式搜索法的局部搜索法虽然不依赖对目标函数的梯度求解，但是有一个缺点就是，如果优化目标的决策向量的维度太高，那么模式搜索算法的收敛速度会非常慢。在求解这类问题的时候如果以过慢的搜索速度来换取较强的局部搜索能力，也是不可取的。
本实施例提出的改进算法正是将模式搜索法中的探测搜索过程做了改进，用高斯因子来取代探测搜索的步长。探测搜索的过程是随机的在轴向方向做试探性的搜索，然后比较搜索到的目标向量和原先目标向量的优劣来判断搜索的成功与否。而高斯因子的加入可以加快这一搜索过程。将这种混合直接搜索算法作为加强粒子群局部搜索的算法命名为DSMOPSO，DSMOPSO的具体改进策略如下：
Step1：设置一个阈值ε和参数GDFlag如公式4-2所示，
Figure BDA0001345512520000071
其中n表示当前Pareto最优解集中粒子的总数，dj表示两代粒子之间的最小距离，也就是计算当前代的粒子和前一代粒子的世代距离，用他们靠近的程度来评价整个种群当前的收敛状态。如果GDFlag在连续三代的搜索过程中都小于阈值ε，那说明此时种群可能已经陷入局部极值，或种群的搜索能力变弱，不能得到更好的解。这时候启用直接搜索法，如果GDFlag连续五代的变化值都在ε范围内，那么算法可能已经找到最终的全局最优解，不启用直接搜索算法；
Step2：从档案中选择一个粒子如
Figure BDA0001345512520000081
D是决策变量的维度。将xk的值赋给yk，依次对每一个元素做探测搜索，搜索步长以高斯算子代替，表示为Gauss。如果f(yk+Gauss)＜f(yk)，则说明探索成功，yk＝yk+Gauss，否则说明探索失败，重复上述工作。如果t＞tmax，则终止搜索，yk＝yk；
Step3：令xk+1＝y，如果f(xk+1)＜f(xk)，则对xk+1沿xk指向xk+1的方向做模式移动，返回Step2，否则进入Step4；
Step4：如果满足迭代次数，则停止运行。
局部搜索算法因为在目标的周围要不断的寻找算法，所以会比较耗费时间，为了不至于太影响算法的收敛速度，因此设置GDFlag这样的参数来检测粒子的收敛状态，只有需要的时候才启用局部搜索算法。这样能够有效的将局部搜索算法和粒子群算法相结合，发挥局部搜索算法的最大效用。
采用的评价指标有收敛性指标GD，多样性指标Δ，误差比ER以及时间参量。
(1)多样性指标Δ
将算法获得的Pareto最优解集按照某个目标函数的大小排序，在目标空间里，和真实Pareto最优解集比较，获得的描述整个Pareto解集分布性能的指标。模型如下,
Figure BDA0001345512520000082
公式(4-3)中di表示相邻两个例子之间的距离，
Figure BDA0001345512520000083
表示所有粒子之间距离的平均值，n表示粒子的总数，d1和df是算法求解出来的边界解和对应真实Pareto最优解中的极端解之间的欧氏距离。
如图2可以看出，如果，d1＝0，df＝0，
Figure BDA0001345512520000084
则说明算法求得的解完全覆盖在了真实Pareto前沿面上，这是一种较为理想的状况。由此说明Δ参数反映算法求得的解相对于真实的Pareto前沿所表现出来的分布性能。计算出来的Δ值越小，说明算法求得的解对于均衡面的分布状况越好。
(2)误差比ER
误差比是描述算法求解出来的Pareto最优解不属于真实Pareto前沿的那些粒子所占的比率，模型如下，
Figure BDA0001345512520000091
公式(4-4)中，n表示算法求解出来Pareto解集中粒子的总数目，对于解集中的每一个粒子，如果该粒子属于真实Pareto前沿，则e取0，否则e取1。因此ER参数值越小，说明解越真实。
将改进后的粒子群优化算法应用在了车辆路径优化问题中，验证了将算法应用在实际问题中后的性能表现。
因此，所述构建车辆成本与客户等待时间的双目标优化模型包括：设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure BDA0001345512520000092
Figure BDA0001345512520000093
Figure BDA0001345512520000094
Figure BDA0001345512520000095
Figure BDA0001345512520000096
Figure BDA0001345512520000097
Figure BDA0001345512520000098
D0j＝D0i+Dij (5-8)
Figure BDA0001345512520000101
Figure BDA0001345512520000102
Figure BDA0001345512520000103
其中，
Figure BDA0001345512520000104
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
S103：对每个目标粒子进行编码并得到编码结果；
在本步骤中，要使粒子群优化算法能够应用在实际应用问题中，需要对每个粒子进行编码。该问题使用的是两行实数编码的形式，假设有6个客户点，4辆车配送，则一个粒子的编码形式可以表示成表5-1的形式。
表5-1粒子的编码
Table 5-1Particle coding
Figure BDA0001345512520000105
其中第一行x1表示车辆的序号，第二行表示车辆运送客户点的顺序，因为种群在寻优过程中，通过更新迭代，会产生非整数，所以对得到的编码要进行取整操作，对x1行取整后得到的结果为表5-2所示。
表5-2取整后编码
Table 5-2After rounding the encoding
Figure BDA0001345512520000106
S105：基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；
在步骤S105中，将每个目标粒子经过步骤S101的模型计算之后，将计算结果均代入步骤S103的编码结果中。
优选地，所述根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作包括：将所述计算结果填入所述实数矩阵中；对x1进行取整操作后，得到每辆车对应的客户点；列出K辆车分别对应的客户点，得到每辆车的行驶路径。
更具体的，对x1行进行取整操作，可以看出，车辆3为客户1、2服务。其中客户1对应的x2的值比客户2对应的x2的值小，说明车辆3的行驶路线为0-1-2-0。以此类推可以得到其他几辆车的路线为。
车辆1：0-4-0；
车辆2：0-6-5-3-0；
车辆3：0-1-2-0。
优选地，所述对所述寻优结果进行解码操作包括：将所述实数矩阵转化为一行数列；将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
具体地，通过对粒子编码可以将实际问题转化为粒子群优化算法可以求解的多目标优化问题，经过迭代后，还需要对粒子进行解码操作，最终得到实际求解出来的方案，根据上一章的假设，6个客户点，4辆车来配送，解码时将两行实数矩阵转化为一行数列，将车辆的行驶路径按照先后顺序排列，在一辆车行驶的路径后面加上车辆的编号，为了避免车辆编号和客户点编号重复，第1辆车用7来表示，依次类推，第4辆车用10来表示。则解码后的数组为：
4 7 6 5 3 8 1 2 9
7、8、9分别表示车辆1、2、3，而7、8、9前面的数字则表示该车所经过的客户点。
以下是对上述车辆调度方法的具体实验：
实验对象中，物流中心坐标为(142,244)，物流中心有7辆运输货物的车，为14个客户服务。客户和车辆的信息如下表格所示，
表5-3客户点信息
Table 5-3Customer point information
Figure BDA0001345512520000111
Figure BDA0001345512520000121
表5-4车辆信息
Table 5-4Vehicle information
Figure BDA0001345512520000122
IMOPSO求解出来的方案和MOPSO算法求解出来的方案做对比，种群大小为50，迭代100次，函数评价次数为5000次。两个算法求解得到的结果如表5-5和表5-6所示。
表5-5MOPSO求解的方案
Table 5-5Solution of MOPSO
Figure BDA0001345512520000123
表5-6IMOPSO求解方案
Table 5-6Solution of IMOPSO
Figure BDA0001345512520000124
Figure BDA0001345512520000131
这些方案分别对应的运输费用和用户等待时间由表5-7和表5-8记录。
表5-7MOPSO的结果
Table 5-7Results of MOPSO
Figure BDA0001345512520000132
表5-8IMOPSO的结果
Table 5-8Results of IMOPSO
Figure BDA0001345512520000133
综合表5-7和表5-8所记录的数据可以看出，IMOPSO求解出来的方案整体上在成本方面比MOPSO有优势，在用户等待时间方面，IMOPSO求解出来的方案有较小的优势，同时，IMOPSO求解出来的方案比MOPSO求解出来的方案多。不过单看表5-8的结果可以看出，虽然各个方案不同，但是成本和用户等待时间几乎稳定在了一定的数值范围内。所以各个方案之间的差别不是特别大，当成本高的时候，用户等待时间就会稍长，用户等待时间短的时候，出车成本就会略高，因此根据物流中心的具体的数据统计和分析可以选择出最佳方案来执行。从结果也可以看出，在实际应用中，改进后的粒子群算法求解出来的方案可以帮助物流中心节省成本的同时给于客户更好的用户体验。
图4为本发明实施例所述的车辆调度装置的结构示意图。
参见图4所示，一种基于多目标粒子群优化算法的车辆调度装置包括：构建模块40，用于构建车辆成本与客户等待时间的双目标优化模型；编码模块42，用于对每个目标粒子进行编码并得到编码结果；计算模块44，用于基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；寻优模块46，用于根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；解码模块48，用于对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度。
优选地，所述构建模块40还用于：设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure BDA0001345512520000141
Figure BDA0001345512520000142
Figure BDA0001345512520000143
Figure BDA0001345512520000144
Figure BDA0001345512520000145
Figure BDA0001345512520000146
Figure BDA0001345512520000147
D0j＝D0i+Dij (5-8)
Figure BDA0001345512520000148
Figure BDA0001345512520000149
Figure BDA00013455125200001410
其中，
Figure BDA00013455125200001411
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
优选地，所述编码模块42还用于：设有M个客户点，表示为：1、2、3…M，K辆车进行配送；第一行用x1表示车辆的序号；第二行x2表示车辆运送客户点的顺序；所述编码结果为所述第一行与所述第二行组成的实数矩阵。
优选地，所述寻优模块46包括：填入模块(图中未示)，用于将所述计算结果填入所述实数矩阵中；取整模块(图中未示)，用于对x1进行取整操作后，得到每辆车对应的客户点；列出模块(图中未示)，用于列出K辆车分别对应的客户点，得到每辆车的行驶路径。
优选地，所述解码模块42包括：转化模块(图中未示)，用于将所述实数矩阵转化为一行数列；排列模块(图中未示)，用于将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
本发明通过对粒子群算法的改进，将多目标粒子群优化算法应用于物流中心的车辆调度问题，以客户等待时间和送货车辆运输成本为优化目标，将实际问题转化为多目标优化问题，进而帮助物流中心节省车辆成本，并给客户更好的用户体验。
以上只通过说明的方式描述了本发明的某些示范性实施例，毋庸置疑，对于本领域的普通技术人员，在不偏离本发明的精神和范围的情况下，可以用各种不同的方式对所描述的实施例进行修正。因此，上述附图和描述在本质上是说明性的，不应理解为对本发明权利要求保护范围的限制。

Claims (8)

1.一种基于多目标粒子群优化算法的车辆调度方法，其特征在于，包括：
构建车辆成本与客户等待时间的双目标优化模型；
对每个目标粒子进行编码并得到编码结果；
基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；
根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；
对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度；
所述构建车辆成本与客户等待时间的双目标优化模型包括：
设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure FDA0002772340410000011
Figure FDA0002772340410000012
Figure FDA0002772340410000013
Figure FDA0002772340410000014
Figure FDA0002772340410000015
Figure FDA0002772340410000016
Figure FDA0002772340410000017
D0j＝D0i+Dij (5-8)
Figure FDA0002772340410000021
Figure FDA0002772340410000022
Figure FDA0002772340410000023
其中，
Figure FDA0002772340410000024
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
2.根据权利要求1所述的车辆调度方法，其特征在于，所述对每个目标粒子进行编码并得到编码结果包括：
设有M个客户点，表示为：1、2、3…M，K辆车进行配送；
第一行用x1表示车辆的序号；
第二行x2表示车辆运送客户点的顺序；
所述编码结果为所述第一行与所述第二行组成的实数矩阵。
3.根据权利要求2所述的车辆调度方法，其特征在于，所述根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作包括：
将所述计算结果填入所述实数矩阵中；
对x1进行取整操作后，得到每辆车对应的客户点；
列出K辆车分别对应的客户点，得到每辆车的行驶路径。
4.根据权利要求3所述的车辆调度方法，其特征在于，所述对所述寻优结果进行解码操作包括：
将所述实数矩阵转化为一行数列；
将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
5.一种基于多目标粒子群优化算法的车辆调度装置，其特征在于，包括：
构建模块，用于构建车辆成本与客户等待时间的双目标优化模型；
编码模块，用于对每个目标粒子进行编码并得到编码结果；
计算模块，用于基于所述双目标优化模型对每个目标粒子进行计算并得到计算结果；
寻优模块，用于根据所述计算结果及所述编码结果对所述每个目标粒子进行寻优操作，得到寻优结果；
解码模块，用于对所述寻优结果进行解码操作，得到目标车辆的最优行驶路径，根据所述最优行驶路径对所述目标车辆进行调度；
所述构建模块还用于：
设定目标物流中心有K辆车，给M个客户点配送货物，则所述双目标优化模型为：
Figure FDA0002772340410000031
Figure FDA0002772340410000032
Figure FDA0002772340410000033
Figure FDA0002772340410000034
Figure FDA0002772340410000035
Figure FDA0002772340410000036
Figure FDA0002772340410000037
D0j＝D0i+Dij (5-8)
Figure FDA0002772340410000038
Figure FDA0002772340410000039
Figure FDA0002772340410000041
其中，
Figure FDA0002772340410000042
表示车辆每公里成本，Ck表示第k辆车出车的固定成本，q表示每个客户点的货物量，g表示车辆载货量上线，v是速度；Dij是点i到点j的距离，D0j是点0到点j的距离；G是扣分函数，在一辆运输卡车按照方案的路线超载的情况下，就增加扣分项，将约束条件(5-3)转化为扣分项加入至所述扣分函数中。
6.根据权利要求5所述的车辆调度装置，其特征在于，所述编码模块还用于：
设有M个客户点，表示为：1、2、3…M，K辆车进行配送；
第一行用x1表示车辆的序号；
第二行x2表示车辆运送客户点的顺序；
所述编码结果为所述第一行与所述第二行组成的实数矩阵。
7.根据权利要求6所述的车辆调度装置，其特征在于，所述寻优模块包括：
填入模块，用于将所述计算结果填入所述实数矩阵中；
取整模块，用于对x1进行取整操作后，得到每辆车对应的客户点；
列出模块，用于列出K辆车分别对应的客户点，得到每辆车的行驶路径。
8.根据权利要求7所述的车辆调度装置，其特征在于，所述解码模块包括：
转化模块，用于将所述实数矩阵转化为一行数列；
排列模块，用于将车辆的行驶路径按照先后顺序排列，并在每一辆车行驶路径的后面加上该车辆的编号，得到每辆车的最优行驶路径。
CN201710555113.1A 2017-07-10 2017-07-10 一种基于多目标粒子群优化算法的车辆调度方法与装置 Active CN107506846B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201710555113.1A CN107506846B (zh) 2017-07-10 2017-07-10 一种基于多目标粒子群优化算法的车辆调度方法与装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201710555113.1A CN107506846B (zh) 2017-07-10 2017-07-10 一种基于多目标粒子群优化算法的车辆调度方法与装置

Publications (2)

Publication Number Publication Date
CN107506846A CN107506846A (zh) 2017-12-22
CN107506846B true CN107506846B (zh) 2021-05-07

Family

ID=60678829

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201710555113.1A Active CN107506846B (zh) 2017-07-10 2017-07-10 一种基于多目标粒子群优化算法的车辆调度方法与装置

Country Status (1)

Country Link
CN (1) CN107506846B (zh)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108197793A (zh) * 2017-12-27 2018-06-22 南京邮电大学 一种基于潮汐模型和粒子群算法的共享单车调配方法
CN108171387B (zh) * 2018-01-16 2021-01-22 清华大学 面向建筑内部的配送路径优化方法及装置
CN108921353B (zh) * 2018-07-06 2021-12-07 上海大学 一种车场配送的优化方法、装置及电子设备
EP3644242A1 (en) 2018-10-23 2020-04-29 Honda Research Institute Europe GmbH System and method for optimizing a service station layout
CN109784592B (zh) * 2019-03-29 2022-08-05 南京邮电大学 基于蒙特卡洛算法与粒子群算法的快递智能小车调度方法
CN110147885B (zh) * 2019-05-07 2021-01-05 浙江大学城市学院 一种改进遗传算法的共享单车停放点分配方法
CN110097231A (zh) * 2019-05-09 2019-08-06 上汽安吉物流股份有限公司 多目标物流调度方法及装置、物流系统以及计算机可读介质
CN112132312B (zh) * 2020-08-14 2022-08-23 蓝海（福建）信息科技有限公司 一种基于进化多目标多任务优化的路径规划方法
CN112488386B (zh) * 2020-11-30 2023-08-15 重庆大学 基于分布熵多目标粒子群的物流车辆配送规划方法及系统
CN112783207B (zh) * 2020-12-31 2022-07-15 哈尔滨工程大学 一种基于多目标粒子群优化的无人机航迹规划方法
CN112906973B (zh) * 2021-03-10 2023-10-24 浙江银江云计算技术有限公司 一种家庭医生随访路径推荐方法及系统
CN112950091B (zh) * 2021-04-19 2024-03-15 深圳市汉德网络科技有限公司 车辆调度方法、装置及存储介质
CN114169832A (zh) * 2021-12-15 2022-03-11 中国建设银行股份有限公司 一种物流配送调度的方法、装置及存储介质、处理器
CN114202214B (zh) * 2021-12-15 2024-04-05 安徽师范大学 一种基于智能网联环境下新能源货车的优化调度方法
CN115130787A (zh) * 2022-08-29 2022-09-30 深圳市城市公共安全技术研究院有限公司 应急资源调度方案的配置方法、系统、终端设备及介质

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104951850A (zh) * 2015-06-25 2015-09-30 广东工业大学 一种求解多配送中心物流运输车辆路径问题的方法
CN104992242A (zh) * 2015-07-01 2015-10-21 广东工业大学 一种求解带软时间窗物流运输车辆路径问题的方法

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104951850A (zh) * 2015-06-25 2015-09-30 广东工业大学 一种求解多配送中心物流运输车辆路径问题的方法
CN104992242A (zh) * 2015-07-01 2015-10-21 广东工业大学 一种求解带软时间窗物流运输车辆路径问题的方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
基于改进蚁群算法的物流配送车辆路径优化研究;张家善;《中国博士学位论文全文数据库 信息科技辑》;20170215(第2期);第18页-19页 *

Also Published As

Publication number Publication date
CN107506846A (zh) 2017-12-22

Similar Documents

Publication Publication Date Title
CN107506846B (zh) 一种基于多目标粒子群优化算法的车辆调度方法与装置
Schmidt et al. Crat-pred: Vehicle trajectory prediction with crystal graph convolutional neural networks and multi-head self-attention
CN107578119A (zh) 一种智能调度系统的资源分配全局优化方法
CN115576343B (zh) 一种结合无人机配送的多目标车辆路径优化方法
CN113867358B (zh) 多无人车协同遍历任务的智能路径规划方法
CN115146866B (zh) 一种考虑实际多约束的多条等效最优路径规划方法
CN111664852A (zh) 一种无人机路径规划方法及装置
CN111007813B (zh) 一种基于多种群混合智能算法的agv避障调度方法
Yao et al. Improved artificial bee colony algorithm for vehicle routing problem with time windows
CN111784072A (zh) 一种车辆路径问题的优化方法及装置
CN110472792A (zh) 一种基于离散蝙蝠算法的物流配送车辆路径优化方法
KR101462337B1 (ko) 유전 알고리즘을 이용한 전기 자동차 재배치 스케줄링 방법 및 장치
Hani et al. Simulation based optimization of a train maintenance facility
CN118469525A (zh) 基于改进nsga-ii的粮面多巡检机器人协同任务分配方法
Liu et al. Multiple depots vehicle routing based on the ant colony with the genetic algorithm
CN117408407A (zh) 一种极端环境下的无人机配送路径优化方法、装置及介质
Zorlu Routing unmanned aerial vehicles as adapting to capacitated vehicle routing problem with genetic algorithms
Ren Solving min-Max vehicle routing problem.
CN115310676A (zh) 一种时变路网下的路径优化方法、装置及存储介质
Lin et al. A q-learning-based hyper-heuristic for capacitated electric vehicle routing problem
Hossain et al. GPU enhanced path finding for an unmanned aerial vehicle
CN112016750A (zh) 一种改进的解决带约束车辆路径问题的方法
CN112308353A (zh) 一种药品仓库作业调度优化方法
CN118822408A (zh) 无人机与车辆协同配送的方法、系统、电子设备及介质
Mahmoodi et al. Framework for truck–RPAS hybrid models in last-mile delivery

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant