多目标交通分配

多目标交通分配（共4篇）

多目标交通分配 篇1

1 引言

在服务经济时代,服务业在整个国民经济中所占的比重不断增加,促进了服务业的网络化、规模化和品牌化经营,服务企业的网络化促进了服务供应链的生成。作为一类重要的服务供应链,物流服务供应链已被广大学者提出并持续研究。目前,物流服务供应链的研究主要集中在对其内涵结构、特征、管理方法、供应商选择、协调机制、合作关系、激励机制和运作动力等方面。而对物流服务供应链中核心企业的订单分配问题的研究则相对较少。

当前对订单分配的研究更多集中在产品供应链领域,且经常与供应商选择问题结合起来进行研究。Narasimhan等(2006)构建了一个多目标规划模型来研究供应链中制造企业的最优供应商数量和最优订单分配的问题,提出了五个不同重要程度的标准来评估供应商的绩效[1]。Amid等(2006)建立了供应商选择的模糊多目标线性规划模型,这个模型能够根据输入数据,帮助决策者找出每个供应商的最优订单数量[2]。Mendoza和Ventura(2008)提出了一个两阶段方法来处理供应商选择和最优订单分配问题,在第一阶段,应用AHP方法基于五个因素的标准对供应商进行评估,在第二阶段,构建一个混合整合非线性规划模型来解决最优订单配置问题[3]。Che和Wang(2008)构建了一个多目标规划模型来研究供应商选择和订单分配,并提出启发式算法对模型进行了求解[4]。Lin在考虑供应商选择标准相互依赖性的基础上提出了一个综合决策模型来研究最优订单分配问题(2009)[5]。Kokangul和Susuz(2009)将AHP和整数多目标非线性规划模型结合起来,基于数量折扣、供应商能力和企业预算三个约束条件,分析了在最好的供应商中配置最优的订单数量[6]。Razmi和Maghool(2009)提出了能力和预算约束下的多内容、多阶段的供应商选择和采购问题的模糊双目标规划模型[7]。Yue等(2010)研究了制造商如何选择关键资源供应商和订单分配数量的问题,提出了启发式算法改进服务水平,减少成本和传递时间[8]。

也有部分学者对物流服务供应链中的订单分配问题进行了研究。刘伟华等(2008)研究了不确定需求的情况下,一个物流集成商面对多个功能物流服务提供商时如何进行订单任务分配的问题,结合物流服务供应链订单任务分配的特点,构建了基于多种物流能力的任务分配模型[9]。周链子,刘伟华(2011)构建了基于匹配能力物流服务的三级供应链模型,研究在随即需求条件下,集成商对提供商、提供商对分包商进行物流服务任务分配决策的问题[10]。姜意扬等(2011)基于集成商对多个物流供应商分配订单的情形,建立了供应商手头订单、能力可获得性、配送效率、缺损率和成本的供应商选择与订单分配组合优化模型,并采用算法进行算例分析[11]。李肇坤等(2009)[12]考虑了港口服务供应链的服务时间、成本、满意度等因素下的物流服务供应链多任务分配模型,并进行了实证研究。

综上所述,以上研究大多采用构建多目标规划模型的方法进行物流服务供应链中分包商选择和订单分配,但是都没有考虑到物流服务供应链中集成商与分包商之间的交易费用,本文在前人研究的基础上,构建了考虑交易费用的物流服务供应链订单分配多目标规划模型,并进行了算例分析。

2 订单分配问题建模

2.1 问题描述与参数设置

考虑由多个物流分包商和一个物流集成商组成的两级物流服务供应链,物流集成商是核心企业,从物流服务需求方处获得物流任务,为了在预定期内完成订单规定的物流任务,物流集成商会将物流任务分配给多个物流分包商来完成,它在其中发挥协调作用。为了建模方便,设置如下参数:

i:物流分包商的序号;

j:物流任务的序号;

t:期间的序号;

Pijt:物流分包商i在t期间内为任务j提供物流能力的价格;

qij:为完成物流任务j物流分包商i能力不足部分与所需物流能力之间的比率;

tij:为完成物流任务j物流分包商i能力延迟供给部分与所需物流能力之间的比率;

Qj:物流任务j可接受的最大的qij;

Tj:物流任务j可接受的最大的tij;

Djt:t时期内物流任务j所需要的物流能力量;

Cijt:t时期内物流分包商i为完成物流任务j所能提供的最大物流能力量;

aij:物流集成商为完成物流任务j从物流分包商i采购物流能力的交易费用;

xijt:t时期内物流集成商分配给物流分包商i的物流任务j的具体订单数量;

Tijt:二进制参数,当在t时期内物流分包商i可以提供物流任务j所需要的物流能力时,Tijt=1,否则,Tijt=0。

Uijt:二进制参数,当在t时期内物流集成商从分包商i处采购为完成物流任务j所需要的物流能力时,Uijt=1,否则,Uijt=0。

2.2 多目标订单分配模型

多目标订单分配问题可以建模如下:

式(1)表示从物流分包商处采购物流能力的总交易费用,(2)表示总采购成本;(3)表示为完成物流订单不足的物流能力总数量;(4)表示总的延迟供给的物流能力数量。

为了实现(1)~(4)目标函数的最小化,这些目标函数需满足以下约束。

约束(5)保证了时期t内物流任务j所需要的物流能力需求量可以被满足;约束(6)保证了不足的物流能力数量小于或等于相应的最大水平;约束(7)保证了延迟供给的物流能力数量小于或等于相应的最大水平;约束(8)分配给备选物流分包商的订单数量小于或等于该物流分包商的物流能力最大供给水平;约束(9)表示在时期t内物流集成商可以将物流任务j的部分订单分配给物流分包商i.

2.3 订单分配模型求解步骤

多目标规划问题的求解,主要是将多目标规划通过适当的方法将其转化为单目标规划。

①可以根据AHP法,确定目标(1)~(4)的权重分别为λ1,λ2,λ3,λ4,且λ1+λ2+λ3+λ4=1,λi≥0,i=1,2,3,4。

②应用加权法将上述(1)~(4)的目标函数表示为

在(11)中,F1n,F2n,F3n,F4n是目标函数(1)~(4)的标准化形式,λ1,λ2,λ3,λ4代表相应目标函数的重要程度。

③原模型就可以转化为如下单目标规划模型

④采用规划软件LINGO11.0进行求解。

3 数值试验

假设有1个物流集成商和3个物流分包商组成的物流服务供应链,其中由物流集成商在物流服务供应链中进行订单分配。i=1,2,3,设λ1=λ2=0.3,λ3=λ4=0.2,t=1,2,3,4,Q1=0.06,Q2=0.09,Q3=0.12,Q4=0.08,T1=0.09,T2=0.12,T3=0.15,T4=0.05,其它参数如表1至表7所示。

通过lingo11.0进行求解的结果如表8所示。

从算例可以看出,考虑交易费用的订单分配多目标优化模型可以实现订单分配的最优化,证明了模型的有效性和可行性。

4 结论

本文研究了单一物流服务集成商面对多个物流分包商时的订单分配问题,在对供应链订单分配模型综述的基础上,构建了考虑交易费用最小化的物流服务供应链订单分配多目标优化模型,基于层次分析法,确定各目标的权重,将多目标模型转化为单目标优化模型进行求解。最后,基于数值试验证明了模型的有效性和可行性。

参考文献

[1]Narasimhan,et al.Multiproduct,multicriteria modelfor supplier selection with product life-cycleconsideration[J].Decision Science,2006,37(4):577～603.

[2]Amid A,et al.Fuzzy multiobjective linear model forsupplier selection in a supply chain[J].InternationalJournal of Production Economics,2006,104(2):394～407.

[3]Mendoza A,Ventura J.An effective method tosupplier selection and order quantity allocation[J].International Journal of Business and SystemsResearch,2008,2(1):1～15.

[4]Che Z H,Wang H S.Supplier selection and supplyquantity allocation of common and non-common partswith multiple criteria under multiple products[J].Computers and Industrial Engineering,2008,55:110～133.

[5]Lin R H.An integrated FANP-MOLP for supplierevaluation and order allocation[J].AppliedMathematical Modeling,2009,33:2730～2736.

[6]Kokangul A,Susuz Z.Integrated analytical hierarchprocess and mathematical programming to supplierselection problem with quantity discount[J].AppliedMathematical Modeling,2009,(33):1417～1429.

[7]Razmi J,Maghool E.Multi-item supplier selectionand lotsizing planning undermultipleprice discountsusing augmentedε-constraint and techebycheffmethod[J].International Journal of AdvancedManufacturing Techenology,2009,(33):379～392.

[8]Yue J,et al.Selecting sourcing partners for a make-to-order supply chain[J].Omega,2010,(38):136～144.

[9]刘伟华,季建华,周乐.两级物流服务供应链任务分配模型[J].上海交通大学学报,2008,42(9):1524～1528.

[10]周链子,刘伟华.基于匹配能力的三级物流服务供应链任务分配模型研究[C]//天津学术文库(下),2011:1441～1453.

[11]姜意扬,王勇,邓哲峰.基于LSSC的供应商选择与订单分配[J].工业工程,2011,14(3):80～86.

[12]李肇坤,郭贝贝,杨赞.港口物流服务供应链中多任务分配问题研究[J].水运工程,2009,(5):39～43.

多目标交通分配 篇2

本文在图着色频谱分配模型的基础上, 提出多目标评价函数, 采用禁忌搜索算法寻找最优解。同时由于禁忌搜索算法中领域移动规则灵活性较差, 对算法求解效率和爬坡能力产生很大影响。因此在领域移动规则中引入高斯柯西变异算子, 改善了算法的寻优能力和效率。在三种不同模式下, 通过实验对比粒子群频谱分配算法和禁忌搜索频谱分配算法的性能。

一、禁忌搜索算法

禁忌搜索算法是一种局部邻域搜索算法, 最早是由Glover提出, 并形成了一套完整的算法。算法的核心是采用局部搜索的方法, 将获得局部最优解放入禁忌表中。

二、基于禁忌搜索的认知无线电频谱分配

2.1模型描述

基于图着色频谱分配模型, 是用可用频谱矩阵、效益矩阵、干扰矩阵和无干扰分配矩阵来描述认知无线电的频谱分配模型。

2.2基于禁忌搜索算法频谱分配算法设计

2.2.1解的初始结构的形成

TS (Tabu Search) 是一种迭代搜索方法, 在本文里提出的基于禁忌搜索算法的认知无线电频谱分配模型, 禁忌搜索算法中的一个解就对应一种可能的无干扰频谱分配矩阵。禁忌搜索算法的解可以表示成:Xi= (xi1, xi2, …, xis) , 其中解的维度和可用频谱矩阵L中值为1的元素个数有关, xis取值为0或1, 表示可用频谱是否分配给认知用户。

2.2.2解的邻域选择

禁忌搜索算中搜索空间的拓展是通过邻域移动的方式实现。禁忌搜索算法的解Xi中的每一维xij (1

其中, j=1, 2, …N, β为一个控制变异步长的常数, G (0, 1) ) 代表的是均值为0, 偏差为1的高斯分布函数产生的随机数。Wj表示前一次更新时分量j的移动距离, Wj’表示本次更新时分量j的移动距离。采用Sigmoid函数将距离转换成[0, 1]的概率值:

由2式可知, sig (Wj’) 代表Xi在相应维上元素取值为1的概率。解xij的更新公式如式3:

采用高斯变异算子避免了随机搜索, 但搜索容易出现过早成熟收敛。本文将柯西算子引入移动距离的更新公式中, 由于柯西密度函数两端较长的分布让柯西变异具有更大范围的变动, 增加了搜索的步长。当迭代次数达到指定值后, 如果当前最优解还没有改变, 则将移动距离更新公式改为式4所示:

2.2.3评价函数

禁忌搜索算法可以根据解对应的分配矩阵An, m计算评价函数的适应度值。本文建立多目标评价函数, 如式5所示:

2.2.4构造算法的藐视准则

当禁忌列表中禁忌解的目标函数值大于最优解的目标函数值时, 就将禁忌解作为更新解, 并更新最优目标函数值。当ST禁忌表中的解存储时间减为0时, 判断其是否为局部最优解, 如果不是可以将该解释放, 如果为局部最优解, 则将该解存储到LT禁忌表中, LT禁忌表存储时间为永久, 使算法避免进入局部最优。

2.3算法流程

基于禁忌搜索算法的频谱分配算法的流程如图1所示。

三、性能仿真及结果分析

本文比较了基于禁忌搜索算法的多目标频谱分配方法和基于粒子群多目标频谱分配方法的性能。设定可用频谱数M=24, 认知用户数N=6, 根据设定目标函数权重的不同, 分别在最大化网络效益 (w1=1, w2=0) 、最大化公平效益 (w1=0, w2=1) 、整体效益 (w1=0.4, w2=0.6) 三种不同模式下进行仿真。禁忌搜索算法参数为:最大迭代次数Tmax=60。粒子群算法的参数设置为:学习因子c1=2, c2=2, 种群大小为50, 最大迭代次数Tmax=60, 粒子速度范围[-5, 5]。L矩阵中元素由随机生成的0、1组成, B矩阵中的元素由随机生成的1到10之间的数组成, C矩阵由随机生成的0、1数组成二元对称矩阵。在多次的仿真实验中L、B、C都不同, 但S是同一次实验不同算法中L、B、C都相同。当M=24, N=6时, 图2、图3和图4分别给出了三种不同模式下禁忌搜索算法和粒子群算法的对比结果, 由图可知, 由于禁忌搜索算法拥有较强的爬坡能力, 解决了陷入局部最优的问题, 禁忌搜索算法在三种不同模式下获得的收益均高于粒子群算法。

四、结语

多目标交通分配 篇3

交通参数的实时检测对城市交通诱导、车辆违章监察等交通监管工作具有重要的意义。基于视频图像的检测方法以其方便实用和信息量丰富等优点而得到了广泛关注[1]。该类方法的检测过程主要包括车辆存在检测、目标提取和参数计算等步骤[2]。其中, 车辆存在检测为基础环节, 目标提取和参数计算为核心环节。

目前的车辆目标提取算法大体可分为背景差分法、光流法和帧间差分法[3,4,5]。背景差分法要获得较好的提取效果, 必须进行背景建模[6], 另外鉴于交通场景中的背景时间渐变性还必须进行背景的动态更新, 算法往往较为复杂, 计算量较大、实时性较差;光流法[7,8]根据图像中每一个不同的运动可以用一组映射参数正确地表达的原理, 通过把具有相同映射参数的光流矢量分配为一类的方法完成目标提取, 提取精度依赖于光流场估算精度, 而光流场的估算精度一直是一个难题, 且算法复杂, 一般难以满足实时性要求;帧间差分法通过对时间上相邻的图像帧直接操作并对所得帧差图像进行处理来完成目标提取, 计算量较小、实时性较强, 但传统的连续帧帧间差分法精度较低。

目前的交通参数计算方法中, 采用的设置虚拟检测线和虚拟检测区域的方法, 虽然保证了检测精度, 但是需要事先固定虚拟线圈在图像中的位置, 灵活性和普适性较差。

本文在上述相关研究的基础上, 针对我国城市混合交通的特点提出了一种基于摄像机标定、改进的离散帧帧间差分、统计滤波和边缘信息处理相结合的多目标参数检测算法, 较好地实现了多车辆目标的提取与参数检测。

1 算法阐述

混合交通场景中多目标参数检测算法的框图如图1所示。算法主要分为摄像机标定、目标检测与边缘提取、交通参数计算3部分。利用对应矩阵法进行摄像机标定;利用帧间差分法结合统计学方法和形态学方法完成目标检测与边缘提取;最终依据目标的外轮廓信息结合摄像机标定结果计算出车流量、各目标车速、车长、车辆面积和交通密度等主要交通参数。

1.1摄像机标定

计算场景中的交通参数是检测算法的目的, 应用中常采用设置虚拟检测线的方法来计算车速目前的摄像机标定方法较多, 考虑交通检测的实用需求, 采用文献[9]提出的基于地面约束和对应矩阵的摄像机标定方法, 首先利用地平面与图像中的对应点建立1个对应矩阵, 然后利用已知的摄像机高度以及地面上垂线 (电杆、标杆等) 在图像中的投影约束信息, 结合文献[10]中的摄像机内外参数求解方法, 完成标定工作。相对于传统标定方法而言, 该方法具有方便灵活、实用性强的特点。

1.2目标检测与边缘提取

1.2.1 车辆差分检测与多目标分割

车辆存在检测是交通参数计算的基础, 在传统帧差法基础上结合实际应用构造差分图像序列, 利用差分序列图像的灰度变化情况完成车辆存在检测;然后对帧差图像进行统计学滤波提取多目标图像。

1) 差分图像的构造。

把来自于视频采集设备的RGB图像序列转换为灰度图象序列IG, 记为IG={Ig1, Ig2, …, Ign}。序列IG中第K帧与第l帧图像相减所得的帧差图像Idkl定义为:

${\rm I}{}_{dkl}(i,j)=\{\begin{array}{l}0,|{\rm I}{}_{gk}(i,j)-{\rm I}{}_{gl}(i,j)|＜{\rm T}\\ 255,|{\rm I}{}_{gk}(i,j)-{\rm I}{}_{gl}(i,j)|\ge {\rm T}\end{array}(1)$

式中:T为差分阈值, 本文取为40。

2) 多目标图像的提取。

据上述差分图像的定义可知, 第K帧与第l帧图像相减所得的帧差图像Idkl中减掉了2帧中灰度相似程度小于阈值T的部分;保留下来的是不同的部分, 既包含了发生移动的车辆在第K帧中的影像也包含了其在第l帧中的影像, 为了滤除Idkl中包含的第l帧中的车辆影像, 构造并运用了统计滤波算法对差分图像序列进行“求同”运算, 完成了Igk对应的多目标图像Idk的获取。本文算法中选取第l、第m和第p帧3帧图像分别与第K帧作差分运算得到帧差序列Idkl、Idkm和Idkp, 然后按下式进行统计滤波

${\rm I}{}_{dk}(i,j)=\{\begin{array}{l}{\rm I}{}_{dkl}(i,j),\text{滤}\text{波}\text{条}\text{件}\\ 0,\text{其}\text{他}\end{array}(2)$

式中:滤波条件构造为:

$\begin{array}{l}\left|{\rm I}{}_{dkm}(i,j)-{\rm I}{}_{dkp}(i,j)\right|\le {\rm T}{}_{dk}\wedge |{\rm I}{}_{dkl}(i,j)-\\ {\rm I}{}_{dkm}(i,j)|\le {\rm T}{}_{dk}\wedge |{\rm I}{}_{dkl}(i,j)-{\rm I}{}_{dkp}(i,j)|\le {\rm T}{}_{dk}。\end{array}$

式中:Tdk为滤波阈值。为获得更好的滤波效果, 选取第l、第m和第p帧3帧图像时, 可使前2帧与第k帧的两两间隔时间较长, 第p与第k帧间隔时间较短的方法实现, 本文取l=k-50, m=k-30, p=k-5。

1.2.2 多目标边缘检测与细化

在多目标图像基础上通过形态学方法提取并细化各目标边缘, 可得多目标边缘图像。如图2所示, (b) 图为 (a) 图监控图像对应的多目标边缘图像。

1.2.3 多目标轮廓提取

在多目标边缘图像中, 目标内部含有大量内边缘像素, 这些像素对后面的交通参数计算意义不大, 本文通过封闭边缘跟踪与包含滤除算法[11]除去了这些点, 完成了各目标外轮廓 (主边缘) 信息的提取, 图2 (c) 为 (b) 的多目标轮廓图像。在多目标轮廓图像中包含了多运动目标的轮廓, 可以通过尺度滤波法滤除掉不完整的目标和不感兴趣的目标 (如行人、自行车等) , 如图2 (d) 所示, 只保留了图2 (c) 图像中的完整汽车目标轮廓 (漏检1辆) 。

1.3交通参数计算

完成多目标轮廓提取与尺度滤波后, 使用如图2 (d) 所示多目标轮廓图像, 运用文献[12]中的方法对目标进行跟踪, 然后结合摄像机标定结果完成各目标车速、车长和车流量等主要交通参数的计算。

车流量是一段时间内通过的车辆个数。跟踪过程中设置车辆计数器, 每当检测到有新的车辆出现则车辆计数器加一, 某时间段内的车流量可通过时间段结束时与开始时的计数器差值获得。

车速的计算中, 首先定义车辆轮廓CT的轮廓重心c, 其坐标 (xc, yc) 为:

$\{\begin{array}{l}x{}_{\text{c}}=\frac{1}{n}{\displaystyle \sum _{i=1}^n}x{}_i\\ y{}_{\text{c}}=\frac{1}{n}{\displaystyle \sum _{i=1}^{n}y}{}_i\end{array},(x{}_i,y{}_i)\in C{\rm T}(3)$

式中:n为车辆轮廓CT所含像素点总个数。

同一车辆目标在差分图像序列第x帧Idx和第y帧Idy中的轮廓重心表示为cx和cy, 则2点在图像中的距离 (车辆位移量) 为:

$S{}_{{\rm I}}=\sqrt{(x{}_i-x{}_j){}^2+(y{}_i-y{}_j){}^2}(4)$

根据摄像机标定参数将SI换算为车辆实际空间位移量SW, 则该车车速可通过下式计算:

$v=S{}_{\text{W}}/(|j-i|\times \text{Δ}{\rm T})(5)$

式中:ΔT为帧采样间隔时间。

车长的计算基于车辆跟踪结果, 根据车辆行驶方向在图像中构造方向线段, 如图3所示, 记线段与目标车辆的轮廓线交点为 (x1, y1) 和 (x2, y2) , 根据摄像机标定参数将上述两点的图像坐标换算为实际空间坐标 (x1W, y1W) 和 (x2W, y2W) , 则车长可通过下式计算:

$L=\sqrt{(x{}_{1\text{W}}-x{}_{2\text{W}}){}^2+(y{}_{1\text{W}}-y{}_{2\text{W}}){}^2}(6)$

2 实验分析

为了验证算法的效能, 基于VC 6.0进行了算法实现, 并对采集于北京西大望路与松榆南路的人车混合交通监控视频进行了参数检测。

1) 对07:20～07:50时段采集的交通视频进行检测, 实际流量467辆, 检测流量441辆, 漏检35辆, 误检9辆, 检出率达94.43%;派实验用车5辆, 循环15次驶过图像采集区, 将算法输出的各车次车长、车速等参数与各车实际参数记录进行比对, 结果显示:车长检测准确率达92.36%, 车速检测准确率达93.27%;

2) 对09:20～09:50时段采集的交通视频进行检测, 实际流量296辆, 检测流量288辆, 漏检8辆, 检出率达97.29%;车长检测准确率达94.19%, 车速检测准确率达95.71%;

3) 对11:20～11:50时段采集的交通视频进行检测, 实际流量385辆, 检测流量371辆, 漏检18辆, 误检4辆, 检出率达96.36%;车长检测准确率达93.05%, 车速检测准确率达92.83%。

分析可见, 算法能够满足混合交通场景中多目标检测的精度要求, 即使在第一时段光照角度较大、阴影影响较重且行人和车辆众多的情况下, 算法也能表现出较为理想的性能。

3 结束语

本文提出的混合交通场景的多目标参数检测算法, 利用对应矩阵法进行了摄像机标定;利用改进的帧间差分法完成车辆的存在检测与轮廓信息提取;通过运用统计学方法对目标轮廓图像进行滤波, 提高了抗干扰能力。算法的主要优点在于运行速度快、实时性好、方便实用且参数检测精度能够满足交通监控的要求。进一步提高目标识别能力和实现场景复现是后继工作的重点。

参考文献

[1]史忠科, 曹力.交通图像检测与分析[M].北京:科学出版社, 2007:3-6

[2]Kastrinaki V, zervakis M, Kalaitzakis K.Asurveyof video processing techniques for traffic applica-tions[J].I mage and Vision Computing, 2003, 4 (21) :359-381

[3]袁基伟, 史忠科.A newsegmentation methodfor i m-age sequence of traffic scenes[C].Proceedings of the5th World Congress on Intelligent Control and Au-tomation, June15~19, P.R.China.2004

[4]介鸣, 黄显林, 卢鸿谦.使用多尺度光流法进行探月飞行器自主视觉导航[J].传感技术学报.2007, 20 (11) :2 508-2 512

[5]章毓晋.图像理解与计算机视觉[M].北京:清华大学出版社, 2003:29-41

[6]谭晓军, 沈伟, 郭志豪.交通场景中运动分割问题的研究[J].计算机工程, 2006, 32 (5) :169-171

[7]董颖.基于光流场的视频运动检测[D].济南:山东大学, 2008

[8]张丽.车辆视频检测与跟踪系统的算法研究[D].浙江大学, 2003

[9]楼建光, 柳崎峰, 胡卫明等.交通视觉监控中的摄像机参数求解[J].计算机学报, 2002, 25 (11) :1 269-1 273

[10]马颂德, 张正友.计算机视觉-计算理论预算法基础[M].北京:科学出版社, 1998

[11]夏楠.交叉路口交通流视频识别及信号灯控制系统[D].沈阳:东北林业大学, 2006

多目标交通分配 篇4

在全球经济一体化的进程中,越来越多的

企业参与全球化生产网络中,与其他企业建立合作关系,分工合作地进行生产与贸易,实现互利共赢,特别是在BTO生产环境下,大量零组件需要外部协作。实现这种协作性生产的一种委托代理加工方式称为OEM(original equipment manufacturing),在这种协作生产方式中,品牌企业如何合理分配订单给不同的代工企业(OEM供应商)进行生产,即生产任务分配问题,就成为这种生产方式的主要决策。

在此类任务分配问题中,一方面每个订单的交货期和售价各不相同;另一方面,承担这些订单的供应商,其加工成本及加工时间也是各不相同的。针对这些情况,为找到一个最优的订单分配方案,就需要考虑成本收益、服务水平等目标因素,以最终达到整体的订单效益最大化。这种多目标分配问题基本模型形式可描述为

min F(x)=(α1f1(x),α2f2(x),…,αnfn(x)) (1)

s.t. x∈S

其中,fi(x)(i=1,2,…,n)为目标分配所要满足并追求的各维度目标(包括成本、时间等)函数;S为多维可行空间[1]。每个目标函数可根据实际情况按一定权重加权评估,其中αi(i=1,2,…,n)为各权重,且满足∑αi=1。

对于订单/任务分配问题,传统的方法包括层次分析法、模糊综合分析法等,考量的评价目标也各不相同。国内外已有学者进行了研究,如考虑成本最低及长期能力,并基于AHP与目标规划方法对外包商选择和任务分配的探索[2];研究制定最小生产时间为目标的任务优化分配策略[3];此外还有从多代理协商合同设计角度确定任务分配机制的研究[4];文献[5,6]分别利用改进遗传算法、灰色理论求解设计优化的任务分配策略。这些研究主要集中在任务分配目标及评价因素选择、新方法应用研究及信息化支持[7]等方面。

与其他研究方法不同,本文采用混合蚁群算法进行研究。蚁群算法(ant colony algorithm,ACA)首先应用于解决经典的TSP问题[8],随后因其自身的并行性、较好的寻优能力等特性在工程优化、流程规划、机器智能、数据挖掘等领域取得了成功的应用。文献[1]应用基本的蚁群算法初步研究了多目标优化问题,并从Pareto改进及种群多样化等方面对算法进行了改进。文献[9]尝试利用蚁群算法解决与多目标任务分配问题相类似的武器分配问题(WTA),在求解离散整数规划上,蚁群算法因其自身的并行搜索机制而具有良好的寻优能力,但基本的蚁群算法在解决大型的NP难题时,常常存在着局部收敛等早熟现象。针对这种情况,许多学者提出了混合算法的思想。其中一个尝试是将易局部早熟的蚁群算法与收敛较慢的模拟退火算法相结合,利用结合蚁群算法搜索高效性和模拟退火算法全局搜索性的混合算法来解决组合优化问题。文献[10,11]提出了结合模拟退火与蚁群算法的混合优化算法,在思路上均以模拟退火作为算法主体,结合了蚁群算法信息素正反馈机制,大大提高了算法求解的寻优能力,但在解种群多样性上略显不足。

本文在前人研究的基础上,首先建立能力约束的多目标的任务分配问题模型;然后利用模拟退火蚁群算法——即以蚁群算法为主体的思路对模型进行仿真求解,实现订单的最优分配,同时对算法在解空间多样性及信息素更新方面做了进一步的改进;最后用数值分析验证了模型与算法的有效性与合理性。

1 带能力约束的多目标任务分配问题的模型构建

多目标任务分配问题可以描述为存在m个不同的订单需要加工完成,现有n个产能不同的OEM供应商可以承担这些订单,因此加工成本和时间各不相同。从成本收益(表现为总的任务利润最大化)及服务水平(表现为交货延误时间最小化)两个目标出发,可建立任务分配的问题模型如下:

$\begin{array}{l}\max {\rm P}{}_{\text{t}}={\displaystyle \sum _{i=1}^m(}R{}_i-{\displaystyle \sum _{j=1}^{n}X}{}_{ij}c{}_{ji})\\ \min {\rm T}{}_{\text{d}}={\displaystyle \sum _{i=1}^m|}{\displaystyle \sum _{j=1}^{n}X}{}_{ij}t{}_{ji}-{\rm T}{}_i|\\ \text{s}.\text{t}.{\displaystyle \sum _{i=1}^{m}t}{}_{ji}X{}_{ij}\le {\rm K}{}_j,\forall j(2)\end{array}$

$\begin{array}{l}{\displaystyle \sum _{j=1}^{n}X}{}_{ij}=1,\forall i\\ X{}_{ij}=\{0,1\},\forall i,j\end{array}$

式中,目标函数Pt为总的加工利润;Td为交货延误时间,即实际订单完工时间与预定的理想交货期的差异;订单i被供应商j加工时状态变量Xi j为1,否则为0;Ri为各订单的售价;Kj为供应商的加工能力或产能;ci j与ti j分别为各订单的生产成本和加工时间;Ti为理想的订单交货期。

由目标函数的约束形式可知:订单必须满足供应商产能,即加工能力约束(约束1);订单具有不可分割性,即一个订单只能由一个供应商加工(约束2)。

最后,如前所述,为方便目标的量化评估,达到效益的最大化,可根据实际情况对两项目标属性进行加权并标准化为求总的适应度最小值。设加工利润权重为α,交货延误时间权重为β,且满足α+β=1,则总的适应度函数可变形为

min(α(-Pt)+βTd) (3)

据此建立多任务分配问题的数学模型。

2 算法设计

针对上述问题,本文采用模拟退火结合蚁群算法的混合智能算法进行求解。其主要思路是首先用随机算法初始化信息素矩阵,然后以蚁群算法为迭代计算的主体,完成一次迭代后,采用模拟退火算法对当前解进行随机扰动产生不同的领域解,在Metropolis接受准则下允许解在有限范围内分散化,产生更多可行解,最后用当前解与改进解所带的路径信息更新信息素矩阵,不断重复上述过程。

在领域的局部搜索中,对当前找到的迭代路径序列进行随机扰动,并按照模拟退火的思想,当扰动解优于当前解时,则无条件接受扰动解;当扰动解次于当前解时,则在当前温度下按接受规则有条件接受或拒绝该解,不断重复这个退火过程直到找到改进后的解。这种做法增加了对当前解的随机扰动,从而扩大了解样本的多样性,并在一定程度上发挥了退火算法的优势,有利于稳定状态的大范围全局寻优。

2.1 任务分配过程的蚁群网络图

构造蚁群网络图如图1所示,假设有m个不同的订单O1,O2,…,Om,n个不同的OEM供应商S1,S2,…,Sn;每个订单都有n个OEM供应商可供选择交付加工,但是一个订单只能选择一个供应商来加工。在Oi处分别设置ri只蚂蚁,每只蚂蚁从Oi(i=1,2,…,m)处根据转移概率转移到各级节点S1～Sn处,完成周游,从而形成一条行走路径,即不同的蚂蚁形成不同的解。这里的处理相当于生成m维的1～n的序列,分别对应于各订单所分配的加工供应商。

2.2 算法相关参数及规则的确定

本算法在计算过程中主要考虑了如蚂蚁各节点转移概率、信息素更新规则、随机扰动策略、退火算法Metropolis接受准则等。

2.2.1 转移概率

理论上,各订单可选择并分配给各供应商,在t时刻,蚂蚁k从某级供应商节点i转移到下一级供应商节点j的概率为

${\rm P}{}_{ij}^{(k)}(t)=\tau {}_{ij}^{(k)}(t)/{\displaystyle \sum _{j=1}^n\tau }{}_{ij}^{(k)}(t)(4)$

其中,τi j表示各级供应商节点之间的信息素浓度;供应商节点的信息素越大,则此供应商被选取的概率越大。

2.2.2 解的领域随机扰动

为增加解样本的多样性,使搜索空间更全面,当蚁群算法产生本次迭代最优路径之后,便在该路径基础上采取逆转策略[12],亦即随机产生两个不同的数,如t1与t2(t2>t1);对应订单分配的解序列两个位置,在此当前解C0中将订单t1与订单t2之间的供应商分配关系(子路径)以反方向插入,其余不变,此时新解为C1。为进一步增加解的多样性,考虑双向逆转策略的改进,即对分配矩阵行列上均使用逆转策略进行扰动。

2.2.3 Metropolis准则

本文考虑在上一步的解领域随机扰动中加入小规模的退火算法过程,即根据退火算法的统计规律,设定初始温度T0(200～280,退火算法中温度为量纲一的量,仅表示初始状态)和退火速率αk(0.8～0.95),一般按照直线函数反比递减。如前所述,按照一定的概率在当前最优路径上随机产生新解,每次接受新解的概率为

${\rm P}=\{\begin{array}{l}1f{}_{C{}_i}\ge f{}_{C{}_j}\\ \exp (\frac{-\text{Δ}f{}_{ij}}{{\rm T}})f{}_{C{}_i}＜f{}_{C{}_j}\end{array}(5)$

Δfi j=fCj-fCi

式中,fCi为当前最优解Ci的适应度;fCj为扰动后产生的新解Cj的适应度;Δfi j为两个解的适应度之差。

从式(5)可以看出,当通过退火算法随机扰动产生新解后,若此解较优于原当前解,则百分之百接受新产生的扰动解为当前解;否则以一定的随机概率有条件地接受或拒绝新解。继续降温,重复下一次温度下的扰动,直至达到设定的最低温度。这里采用了模拟退火算法的思想,允许目标函数在有限范围内变坏,增加了解抽样的多样性,有效地避免了计算过早地陷入局部最优状况。

2.2.4 信息素更新规则

在融合模拟退火算法Metropolis扰动之后,其更新方程为

τi j(t+1)=ρ τi j(t)+Δτ (6)

$\text{Δ}\tau =\{\begin{array}{l}\frac{Q}{f{}_{\text{C}}}ij\text{为}\text{当}\text{前}\text{解}\text{路}\text{径}\\ 0\text{其}\text{他}\end{array}(7)$

式中,τi j(t)为t时刻路径上的原信息素浓度;ρ为信息素强度的持久性系数(0.5～0.9);Δτ为本次迭代计算的信息素增量;Q为一正的常数;fC为目标函数适应度值。

最后要提及的是,在目标函数的处理上,本文借鉴了大M法的思想,对超出约束的解引入惩罚系数,从而有利于模型在程序实现上的处理。

2.2.5 算法求解步骤

混合算法程序伪代码如下:

(1)初始化

相关参数的设定及任务、供应商信息的读入;

NC=1:NC_max;//NC为迭代计算次数;NC_max为规定的最大循环次数

τ=C;//信息素浓度初始化,C为初始化信息数

Initial(τ);//随机算法初始化信息浓度

Δτ=0;//信息素增量置0;每次更新取C/5左右效果为佳

Tabuk=Φ;//蚂蚁k的分配路径表清零

k=1;Ant_number;//k为蚂蚁编号;Ant_number为蚂蚁个数

(2)蚂蚁重复周游寻解

while NC⇐NC_max do

for k=1:Ant_number do

蚂蚁k以概率P(k)i j为订单i选择下一供应商j;//见式(4)

Tabuk(NC)=j://供应商j写入分配路径表

(3)适应度目标值计算

for k=1:Ant_number do

for i=1:M do

for j=1:N do//M为订单数,N为供应商数

计算总的加工收益Pt与服务水平Td,并加权处理;//见式(3)及模型(2)

(4)退火算法领域搜索

设定退火算法相关参数;

T0=U;//定义初始温度,常数U代表某高温状态

while T>T_acceptionp and Makob=1∶L do;//T_acceptionp为最低温度点,Makob为链长,并判断迭代次数是否到达设定链长

exchange(Ci,Cj);//行列双向的逆转策略与随机扰动

if (E) AcceptNewSolution(Ci,Cj)

else disturbance(Ci,Cj);//以Metropolis规则判断本次迭代两解优劣,并决定取舍

end if

T=T*α;//降温

(5)信息素更新

for k=1:Ant_number do

for j=1∶N do

$\text{Δ}\text{τ}{}_{\text{i}\text{l}}=\frac{\text{c}{}_1}{\text{f}{}_{\text{i}\text{t}\text{e}\text{r}}(\text{n}\text{c})}+\frac{\text{c}{}_2}{\text{f}{}_{\text{g}\text{l}\text{a}\text{b}\text{a}\text{l}}}$;//按式(7),具体可考虑同时更新扰动前后两解的路径信息

τi l(nc+1)←ρ τi l(nc)+Δτi l;//参见式(6)

(6)最终计算结果

if未到达结束条件,返回第(2)步;

else记录并输出最终解

3 算例分析

为了验证本文构建的模型与算法的有效性,本文用两算例(单资源约束与多资源约束)来进行数值模拟分析。

(1)算例一:单一资源约束情况

只考虑加工时间的单资源约束时,假设某品牌制造商接到9个不同顾客的订单(生产任务),每个订单的交货期与售价见表1。

现有5个OEM供应商可以承担这些订单,但是成本及加工时间不同,同时各供应商也有生产能力上的限制,具体见表2。其加工时间及成本信息见表3,例如4/18中4表示加工时间,18代表订单加工成本,依此类推。此外,根据该品牌制造商追求目标的侧重特点,对式(3)中选取加工利润权重系数为α=0.3,交货延误时间权重为β=1-α=0.7。

本文采用MATLAB仿真编程工具,依次利用单纯的模拟退火算法、蚁群算法及混合SA-ACO算法进行订单的分配问题求解,单资源约束仿真实验结果分别如图2～图4所示。

经多次仿真实验,三种算法均能以其自身的寻优性能求解出此简单算例的最好解,求解出的最佳订单分配矩阵见表4。即供应商1负责订单4;供应商2同时负责订单7与8;供应商3负责订单6;供应商4负责订单1、5和9;供应商5负责订单2与3,具体对应的订单分配矩阵结果如表4所示。此时,可由此算出加工利润Pt目标函数值为285万元,交货延误时间Td目标函数值为89d,按照式(3)赋权加总的最小适应度值为-23.2。

(2)算例二:考虑多种资源约束的情况

综合考虑加工时间和关键物料的多资源约束时,其他条件不变,假设各订单的加工关系到某种关键物料的使用,使用情况wi如表2中最后一列数据所示;此时就要考虑OEM供应商在加工这些订单时有关键物料可用量的资源约束Wj,可用量具体如表3所示。亦即在原模型基础上加入如下新约束:

${\displaystyle \sum _{i=1}^{m}w}{}_{i}X{}_{ij}\le W{}_j,\forall j$

据此用同样的仿真实验求解过程,由实验结果可得,混合算法在问题复杂度增大的情况下依然能保持良好的求解效率,求解出的最佳订单分配矩阵如表5所示。同理,加工利润Pt目标函数值为284万元,交货延误时间Td目标函数值为97d,按照式(3)赋权加总的最小适应度值为-17.3。多资源约束情况下混合算法及基本蚁群算法的仿真实验结果如图5、图6所示。

在单一资源约束情况下,从图2可以看出,模拟退火算法具有很好的全局搜索性能;但是由于反馈信息利用不足,收敛速度较慢,直到100多次迭代计算才收敛至最优解,而且求解结果并不稳定,耗时较长;而在加入多资源约束考虑时,相同的计算时间内甚至很少找到最优解。从图5及图6可以看出基本蚁群算法相对快速的搜索能力,在60～70次左右便能找到最优解,有时也容易陷入局部收敛;而加入自适应条件与退火搜索的混合算法无论在收敛速度还是在寻优的稳定性上均优于前两者,基本上结合了两种算法的长处:最好情况下,在20次左右迭代计算便能找到最优解,经笔者多次实验,其最佳寻优次数也平均多于单一算法情况,具有较好的鲁棒性。

本文也利用商业优化软件Lingo11.0对该问题进行了求解,得到与混合算法相同的结果。经笔者多次实验,对每种计算方法都重复10次求解,各方法计算结果(包括多资源约束情况)统计分析与对比见表6。由此可证明各算法的自身求解能力及混合算法的有效性。

注:表中的负值为适应变值(量纲一),其值越小越好。

4 结束语

任务分配问题是当前供应链协作环境下普遍存在的问题。本文建立了多目标的订单分配模型,并尝试通过结合具有全局搜索性的模拟退火算法及有快速寻优性能的蚁群算法,来对此类问题进行求解。希望借以充分利用两算法的优势,克服如退火算法收敛慢、蚁群局部收敛的缺陷,在新解的扰动中加入了退火算法的规则,有效提高了搜索空间的多样性。最终对基本模拟退火算法、基本蚁群算法、混合算法三种方法的同算例求解结果进行了对比,可以证明混合算法在求解速度及质量上都有让人满意的效果。

参考文献

[1]池元成,蔡国飙.基于蚁群算法的多目标优化[J].计算机工程,2009,35(15):168-172.

[2]朱云.目标规划及AHP在企业外包任务分配中的应用[J].吉林省经济管理干部学院学报,2010,24(3):23-26.

[3]何霆,郭世伟,徐汉川.基于最小生产时间的制造任务分配策略[J].黑龙江大学自然科学学报,2009,26(5):591-595.

[4]谢经明,娄平,陈幼平,等.供应链中基于多Agent协商的任务分配机制的研究[J].中国机械工程,2005,16(21):1911-1915.

[5]郭志明,莫蓉,孙惠斌.改进GSA算法在协同制造任务分配中的应用[J].计算机工程与应用,2011,47(14):210-213.

[6]张卫,潘晓弘,田景红,等.基于灰色理论的制造任务分配服务研究[J].中国机械工程,2010,21(14):1694-1703.

[7]朱金达,宋海生,张永弟.网络化制造执行系统任务分配的研究[J].设计与研究,2006,7(33):9-11.

[8]Dorigo M,Ganbardella L.Ant Colony System a Co-operative Learning Approach to the Traveling Sales-man Problem[J].IEEE Trans.on Evolutionary Computing,1997,1(1):53-66.

[9]罗德林,段海滨,吴顺详,等.基于启发式蚁群算法的协同多目标攻击空战决策研究[J].航空学报,2006,27(6):1166-1170.

[10]刘少伟,王洁,杨明,等.防空C3I目标分配问题的ACO-SA混合优化策略研究[J].系统工程与电子技术,2007,29(11):1886-1890.

[11]麻士东,龚光红,韩亮,等.目标分配的蚁群_模拟退火算法及其改进[J].系统工程与电子技术,2011,33(5):1182-1186.