柯良军;尚可;冯祖仁
【摘 要】针对物流配送系统优化设计中关键难题之一的团队定向问题,提出了一种部分顾客需求动态到达的动态团队定向问题,并建立了该问题的模型.采用把规划周期分成一系列时间段的策略,将动态问题转化成一系列的静态子问题求解.提出了一种蚁算法,其特点是利用上一时间段的信息来加速算法寻优能力,并用一种基于分支定价的离线精确性算法来求解动态团队定向问题.实验结果表明,与基于分支定价的离线精确性算法相比,所提出的蚁算法能在1 ks内求解4个测试算例,并且在2个算例中得到的最好解优于离线精确性算法的解.%A dynamic team orienteering problem of partial dynamic arrival customers is studied,and a model of the problem is established to deal with the team orienteering problem, which is one of the most critical problems in the optimization design for logistic distribution system. The dynamic problem is converted into a series of static sub-problems by partitioning the planning horizon into a series of time segments. An ant colony optimization (ACO) based algorithm is proposed to solve the resulting problem. The prominent characteristic of the alg orithm is to use the information obtained from the last time segment to enhance the search behavior. An exact offline algorithm based on branch and price is also presented to solve the problem. Experimental results and comparisons with the exact offline algorithm based on the branch and bound show that the proposed ACO-based algorithm can solve four test instances within 1 000 seconds, and that the solutions of two test instances obtained by the proposed ACO-based algorithm are better than those obtained by the exact offline algorithm.
【期刊名称】《西安交通大学学报》
【年(卷),期】2011(045)006
【总页数】7页(P1-6,54)
【关键词】动态团队定向问题;蚁算法;分支定价
【作 者】柯良军;尚可;冯祖仁
【作者单位】西安交通大学机械制造与系统工程国家重点实验室,710049,西安;西安交通大学机械制造与系统工程国家重点实验室,710049,西安;西安交通大学机械制造与系统工程国家重点实验室,710049,西安
【正文语种】中 文
【中图分类】TP301.6
团队定向问题(TOP)是一类特殊的物流配送路径优化问题.该问题是指在满足一定约束条件下,为了服务一组具有一定报酬的顾客,规划车辆行程以最大化车队的总收益.1994年,Butt等[1]最先研究团队定向问题,不过他们称这类问题为多路最大收益收集问题.团队定向问题这一名称是由Chao等[2]于1996年确立的.近几年,国内外学者针对该问题提出了许多高效的算法,文献[3-4]中分别提出了列生成和分支定价两种精确性算法.由于团队定向问题是一类NP-hard问题,现有研究主要集中于启发式算法.Chao等[2]提出了5步法,Tang等[5]提出了一个禁忌算法,Archetti等[6]提出了两个禁忌算法和一个变邻域算法,Ke等[7]用蚁算法来求解等.文献[8]综述了现有的主要研究成果.
3c技术
不过,现有研究都只考虑静态模型,即在规划过程中模型是不变的,实际上随着时间的延续不断有新的客户需要服务.比如某家电公司维修员要给分布在城市各地的顾客提供维修服务,但是在规划周期的开始(例如一天的上午9点钟),只有一定比率(例如45%)的顾客需求已知,其余的顾客需求会在以后的时间内随机到达.只有等到顾客需求到达的时刻,顾客需求的地理位置和收益才被确定.这就意味着在规划周期开始,规划好的最优路线可能不再是最优的.在这种情形下,需要重新规划行程安排以满足需求.为解决该问题,本文研究这类顾客信息变化的团队定向问题,简称动态团队定向问题.
所考虑的动态团队定向问题与静态团队定向问题的主要区别在于,动态团队定向问题是把规划周期分割成一系列时间段,在每个时间段上解决相应的静态团队定向问题.每个静态团队定向问题只考虑当前存在的并且未被服务的顾客需求.在文献[4]的基础上,采用一种离线精确性算法——离线分支定价算法来求解.注意到团队定向问题是NP-hard的[7],这种离线精确性算法的计算复杂度不是多项式的,只适用于小规模问题.为此,本文给出动态团队定向问题的数学模型,提出了一种蚁优化算法,它利用上一时间段的信息来加速算法的寻优能力.实验表明,所提出的蚁算法能在较短的时间内搜索到高质量的解.
mocvd
假设顾客i出现的时间为ti,其中0≤ti≤H,0表示规划周期的开始,H表示规划周期的结束,在区间[0,H]动态出现的顾客信息不能提前预知.令(xi,yi)为顾客所在的位置(本文假设所有顾客位置分布在一个平面上),ri为服务该顾客的收益,则每个顾客的信息可以用一个向量Pi=(ti,xi,yi,ri)来表示.车辆数目为m,车辆最长运行时间为Tmax,车辆只能从起点出发一次.另外,不失一般性,假设车辆速度恒定为1.
动态团队定向问题可以描述为:在规划周期内指派车辆去服务已经存在的顾客(包括在0时刻已经存在的和以后随机到达的顾客),使得所服务顾客的收益最大化.
考虑到当一个新的顾客需求出现时就立即进行路径调整是不实际的,本文将规划周期划分成一系列时间段,在每个时间段上的路径规划问题就转化为一个静态团队定向问题.每个时间段上的静态团队定向问题只考虑当前存在的并且未被服务的顾客需求.注意到,所确定的静态团队定向问题的车辆是多起点类型的,而不是单起点的,并且车辆可以转向,即当车辆在行驶途中,如果一个新的解产生,车辆可以立即执行新的规划,有可能离开当前目的地转向新目的地.经纬线
每个时间段上的静态团队定向问题描述如下.
图书管理系统论文
给定一个完全无向图G=(V,E),其中V={1,…,n}是顶点集,E={(i,j)|i,j∈V}是边集.每个顶点i都有收益ri.起点为多起点,包括出发点1和目前车辆所在点,终点为点n,点i和j之间的距离表示为cij.相应的静态团队定向问题就是出最多m条从多起点出发到终点终止的路径使得所经过点的收益最大化.每个点最多只能经过一次,每辆车的剩余最长运行时间表示为 T′max.根据文献[7]中对静态团队定向问题数学模型的描述,本文给出每个时间段上的静态团队定向问题的数学模型.
采用以下记号:
(1)如果车辆k经过点i,则 yik=1,否则yik=0;
(2)如果车辆k经过边(i,j),则 xijk=1,否则xijk=0;
(3)nts为时间段数量;
(4)Nt为第t个时间段的顾客集,t=0,…,nts;crh2
(5)Qt为第t个时间段的车辆集,t=0,…,nts.
基于以上记号,第t个时间段上的静态团队定向问题的数学模型为
其中第1个约束规定路径的连通性,第2个约束规定每个顾客最多经过一次,第3个约束描述了时间约束.最后2个约束保证了变量必须取值为整数.
蚁算法(ACO)是一类应用广泛的智能优化算法,其突出特点是正反馈和分布式计算,具有良好的适应性、鲁棒性、分散控制及自组织等特点.下面给出一种求解动态团队定向问题的蚁算法.
本文所提出的动态蚁算法是基于划分时间段的思想,把规划周期[0,H]划分成nts个等间距的时间段,每个时间段的长度为 H/nts,在一个时间段的结束时刻处理在这个时间段内出现的顾客需求.在每个时间段内,确定一个静态团队定向问题,然后用ACO求解相应的静态团队定向问题.数码彩扩
在每个时间段的结束时刻求得一个解,同时也可估计车辆在该规划下经过一个时间段后的位置、行驶时间等信息.
这里需要考虑3个问题:①如何构造时间段上的静态团队定向问题;②如何用ACO算法去解决
相应的静态多起点团队定向问题;③需要一种信息素传递策略,把一个时间段求得的规划信息传递给下一个时间段,以利于提高算法搜索性能.下面将详细讨论这3个问题.
整个ACO-DTOP算法的伪代码表示为:
初始化车辆起点为1,在0时刻之前已知的顾客集为N0;
设初始顾客集为N0.记第i个时间段上的静态团队定向问题为Pi,Pi在第i个时间段的开始时刻产生,结果在第i个时间段的结束时刻求得,记为Si,即求解Pi的时间长度为时间段的长度H/nts.在Pi求解的过程中,Si-1执行,记Ci-1为Si-1执行期间被服务的顾客集,Oi为Si-1执行期间新到达的顾客集.Pi考虑的所有顾客集记为Ni,则 Ni=Ni-1\Ci-1∪Oi-1,整个过程可以由图1描述.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议