New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

A novel routing scheme in OBS network with sparse wavelength conversion capabilities

The overall burst loss probability is the primary metric of interest in an optical burst switching network with sparse wavelength conversion capabilities (SWCC-OBS). With the overall burst loss probability as the optimization objective, one has to solve an integer nonlinear programming (INLP) problem. In order to overcome the computational difficulties we propose a fictitious play method to approximately solve the INLP. Consequently, a randomized routing strategy can be achieved. The simulation results show that the proposed strategy can give a near-optimal route that avoids the conflict of burst data effectively and decreases the overall burst loss probability. At the same time it also performs well in balancing loads throughout the whole network under different kinds of burst traffic pattern.     

基于局部路由策略的复杂网络拥塞控制

提出一种复杂网络上的局部路由策略,算法采用节点收缩法评估节点的重要度,发送节点根据邻居节点的重要度及网络的状态自适应地调整向邻居节点转发数据包的概率.在网络处于自由流通状态时充分发挥关键节点的优势,保证数据包快速到达目的地;在网络处于即将拥塞时分散业务,根据节点重要度准确识别网络中的关键节点,通过有效分流予以保护.仿真结果表明:在网络处于自由流通状态时,该局部路由策略能充分发挥网络中关键节点的枢纽作用,保持较低的传输时延;在网络部分关键节点出现拥塞时,该局部路由策略能有效避开拥挤严重的节点,将数据包均匀地分布在各个节点上,有效抑制网络拥塞,提高网络的容量.     

软件定义广域网中基于IPv6分段路由的双栈流量调度算法

针对当前软件定义广域网在应对企业园区部署双协议栈出口链路、园区之间支持双协议栈通信的网络架构下,存在园区任意协议栈出口链路失效时,园区间双栈流量不可通信的问题,提出了一种适用于软件定义广域网的IPv4/IPv6双协议栈环境下的流量调度算法。该算法基于快速重路由机制,通过结合基于IPv6的分段路由技术分为路径编码算法和报文处理算法2部分实现。在广域网双栈出口任一链路失效时将不同园区的双栈流量进行调度。通过在Mininet中的仿真模拟验证了算法的可行性,并利用带宽测量工具iPerf对链路性能进行测量,测量数据表明利用双栈流量调度算法进行双栈流量调度极大地提高了园区间双栈链路的利用率和服务质量。     

无人机自组网中改进型反应-贪婪-反应路由协议

无人机自组网具有网络拓扑变化剧烈,链路断开频繁等特点.反应-贪婪-反应(reactive-greedy-reac-tive,RGR)路由协议是针对无人机自组网而提出的改进型协议,在高动态环境下具有较好的网络性能.针对RGR协议具有网络开销大、易出现网络拥塞等问题,提出了一种基于负载均衡和高贪婪地理转发成功概率的改进RGR路由协议.该协议在RGR协议的基础上,提出基于节点负载状态和地理位置信息辅助的受限洪泛机制、GGF模式下高分组成功传输概率的路径选择策略和基于节点负载预测和运动特征的分组转发策略3项关键改进措施.仿真结果表明,相较于AODV和RGR及其改进型协议,该协议提高了分组投递率,降低了网络的控制开销和平均端到端时延,提升了网络应对拓扑高度动态变化的能力,有效改善了网络性能.     

基于聚类非支配排序的电动物流车路径规划及充电策略

电动物流车电池容量有限、充电时间长以及配套设施不健全等问题制约着其在物流配送领域中有效推广.为此,提出基于聚类非支配排序算法(AP-NSGA-Ⅱ)来解决电动物流车的多目标路径优化问题,建立了一种充电策略,通过设计加权AP聚类划分配送簇,避免初始种群的随机性和盲目性,簇内配送点规模降低了非支配排序算法的运行时间和复杂度,根据充电站的分布和距离关系,电动物流车执行部分充电策略.最后,通过仿真实验证明该算法的有效性,比较了电动物流车满充和部分充电条件的差异.     

Improved approximation for the capacitated inventory access point problem

The Inventory Access Point (IAP) is the single-item lot-sizing problem where a single customer faces demands in a discrete planning horizon, and the goal is to find a replenishment policy that minimizes the total inventory and ordering costs. While the uncapacitated version is polynomial, only a 3-approximation is known for the capacitated case. We improve this factor to 2.619 and, as a byproduct, we also improve the best factor for SIRPFL, which is a variant with multiple depots and customers.     

求解带时间窗车辆路径问题的混合Memetic算法

为提高带时间窗车辆路径问题的求解精度和求解效率,设计了一种混合Memetic算法。采用基于时间窗升序排列的混合插入法构造初始种群,提高解质量的同时兼顾多样性,扩大搜索空间;任意选择组成父代种群,以维持搜索空间;运用简化的变邻域搜索进行局部开发,引入邻域半径减少策略提高开发效率,约束放松机制开放局部空间;以弧为对象,增加种群向当前最优解和全局最优解的后学习过程。实验结果表明,所提出的算法具有较好的寻优精度和稳定性,能搜索到更好的路径长度结果,更新了现有研究在最短路径长度的目标函数上的下限。     

考虑横向整合战略的库存路径动态区域定价

库存路径和定价是供货商管理库存(Vendor Management Inventory, VMI)中三个互相制约和影响的决策问题,是降低供货商成本,提高其利润的关键。针对VMI拉式供应链中多供货商、多商品和多区域的库存路径定价问题,提出了对不同区域客户、在不同时段进行商品差异化定价策略,并设计一种共同配送车辆司机成本和燃油成本分摊方案,据此构建基于横向整合战略的库存路径动态区域定价模型。算例结果显示,在横向整合战略下,供货商商品定价会有所降低,配送车辆行驶距离显著缩短,各时段配货量更为均衡,期末库存数量显著降低。研究表明,无论供货商之间供货规模比例差异多大,开展库存路径动态区域定价,供货商联盟成员的利润均能得到显著提高,实现合作共赢的目标。     

基于成本和加班时长的双目标家庭护理人员调度问题

人口老龄化程度的持续加重使得家庭医疗护理服务逐渐发展。本文针对家庭护理人员调度优化问题,考虑医患的技能匹配、加班费用、加班时长和工作量分配的均衡性等因素,设定最大技能偏差和工作时长,建立了最小化运营成本和最小化最大加班时长的双目标混合整数规划模型。设计了改进的NSGA-II和SPEA-II算法对问题进行求解,数值实验表明:最大加班时长越长,运营成本越小;最大技能偏差和医护人员早到惩罚对目标的影响明显;小规模算例中两算法均表现良好,大中型规模算例中改进SPEA-II的效率更高。