时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

快件揽收实时车辆路径问题的一种贪婪算法

快递运营中，调派车辆前往随机发生的快件发件人处上门揽收快件，是一个实时编排行车路径的动态决策过程．本文针对该问题，采用了揽收所有快件的最后时刻最早和行车路径最短的目标，结合车辆揽收快件数平衡的要求，给出一种贪婪算法；然后，对Solomon设计的100个点规模的VRPTW算例做计算试验，分析了车辆数对目标的影响．     

基于AGV的智能仓库系统储位分配问题研究

研究了基于自动引导机器人(AGV)的"货到人"拣选模式下的智能仓库系统补货阶段的储位分配问题.根据待拣选订单信息计算出商品之间的关联度,考虑了货架上存放的物品信息、空余储位数量、待补货物品信息,以同一货架上的各种商品之间的关联度之和最大化为目标函数,建立了补货阶段储位分配问题的整数规划模型;设计了求解模型的贪婪算法,并分析了算法复杂度.利用一个具体实例进行模拟计算,分析了贪婪算法的求解效果.进一步利用不同规模算例进行模拟计算,分析了贪婪算法的计算时间和近似比,结果显示贪婪算法可以在很短的时间内得到近似最优解,近似比不超过1.15.设计的贪婪算法可以作为智能仓库管理信息系统的核心算法.     

应急物资联合配送决策研究

救援物资的高效投放是应急物流的关键活动之一。考虑到灾后救援车辆短缺,分配时受灾群众产生非理性心理,以及灾后道路状况对军、地救灾车辆速度产生影响等因素,本文从军民融合的角度出发,根据军地运输车辆特点,设计科学合理的车辆分配方案与运输路线。论文研究构建了基于车辆分配公平性和应急配送及时性的“分配-运输”集成决策模型,设计改进后的NSGA-Ⅱ算法进行求解,最后通过算例验证本算法的有效性和合理性,并通过调节军民运输车辆数,找到应急救援过程中的最佳军、地车辆比例,从而为灾后各灾备中心的车辆调度决策提供参考。     

基于改进萤火虫算法的开放式车辆路径问题

针对带软时间窗的多配送中心开放式车辆路径问题,提出了一种新改进的离散萤火虫算法,采用基于贪婪思想的随机邻域搜索策略来提高算法的局部和全局寻优能力;研究了一种步长自适应的方法,其根据当前迭代个体和进入下一次迭代的个体之间的距离自动调整步长,大大提高算法的精度和收敛速度.仿真实验表明了新改进算法的有效性及可行性.     

多目标定位路线问题模型及禁忌搜索算法研究

在一个完整的物流系统中,总费用和工作量平衡是影响决策的两个基本标准,拓展对员工重要的公平原则-工作量平衡,并权衡工作量与总费用之间的平衡.在此基础上,考虑了带路线分配决策的多目标定位-路线问题,建立了数学模型,采用禁忌搜索算法对模型的求解,为检验车辆多次使用的效果,针对算法设计了联立和序贯两种不同的车辆路线分配形式.算法分析结果表明:区域特征在区分算法两种形式的性能时具有重要的地位.     

基于“货到人”拣选模式的储位分配问题研究

研究了“货到人”拣选模式下的储位分配问题,以订单拣选过程中搬运货架总时间最短为目标建立了整数非线性规划模型,并证明其为NP-hard问题,分别设计了求解模型的贪婪算法和单亲进化遗传算法。首先根据订单和物品的关联关系对物品进行聚类,基于聚类结果设计了求解模型的贪婪算法。然后设计了直接求解模型的单亲进化遗传算法,遗传算法中采用了0-1矩阵编码、多点基因倒位算子、单点基因突变算子和精英保留等策略,通过合理选取参数,能够很快求解出问题的近似最优解。最后利用模拟算例和一个具体实例进行计算,并对贪婪算法和遗传算法的求解时间和求解效果进行了比较分析。结果显示,对于小规模问题,两种算法均能在较短的时间内以很高的概率得到问题的全局最优解,对于中等规模的实际问题,利用两种算法得到的储位分配方案均优于企业目前采取的基于出库频率的储位分配方案,遗传算法得到的储位分配方案对应的货架搬运次数、货架搬运总时间等均优于贪婪算法。本文设计的遗传算法可以作为智能仓库管理信息系统的核心算法。     

求解车辆路径问题的免疫算法

将免疫算法用于求解车辆路径问题,并根据车辆路径问题的具体情况提出了一种基于分组匹配的亲和力计算方法.实验结果表明,免疫算法能有效地应用于车辆路径问题.     

带时间窗车辆路径问题的改进节约算法

对节约算法进行了改进,并利用改进的节约算法解决了带时间窗约束的多类型车辆路径问题．首先讨论了带时间窗约束的单类型车辆路径问题,给出其模型,并归纳了几种通过改进传统的节约算法得到的用于求解带有具体约束车辆路径问题的改进节约算法．     

免疫算法在车辆调度问题中的应用

免疫算法是模仿生物体高度进化、复杂的免疫系统仿生的一种智能化启发式算法。本文根据车辆调度问题的具体情况，应用免疫算法解决车辆调度中路线安排问题，并提出了一种基于分组匹配的亲和力的计算方法。实验结果表明，免疫算法能有效地应用于车辆调度中路线安排问题。     

Effective Heuristic Procedures for a Field Technician Scheduling Problem

This paper addresses a field technician scheduling problem faced by many service providers in telecommunication industry. The problem is to assign a set of jobs, at different locations with time windows, to a group of field technicians with different job skills. Such a problem can be viewed as a generalization of the well-known vehicle routing problem with time windows since technician skills need to be matched with job types. We designed and tested several heuristic procedures for solving the problem, namely a greedy heuristic, a local search algorithm, and a greedy randomized adaptive search procedure (GRASP). Our computational results indicate that GRASP is the most effective among them but requires more CPU time. However, the unique structure of GRASP allows us to exploit parallelism to achieve linear speed-up with respect to the number of machines used.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

基于背包模型的人员优化配置问题

运用背包模型解决油库人员在各岗位的优化配置问题,并运用贪婪算法进行求解.考虑到各人员的总工作时间的均衡性,运用反向排序的方法对原有的贪婪算法进行改进.最后,通过举例对两种算法进行评价.     

Heuristic algorithms for a complex parallel machine scheduling problem

In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows. This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given feasible solution of the problem. This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405.     

现金押运路线问题——基于多类型的风险

以人民币现金押运为研究背景,考虑了一种基于多类型风险的现金押运路线问题,以在途风险成本、库存现金风险成本以及运输成本为优化目标,建立了混合整数线性规划模型,并提出了一种基于多样化策略和改进邻域搜索的混合遗传算法,其中遗传算法对押运路线进行选择,贪心算法用来求解各类风险指标。数值实验分别对问题特性和算法性能进行了分析。实验结果表明:1)混合遗传算法能求解更大规模的问题,得到较好的解,并很好地平衡了运行时间和求解质量;2)多类型风险影响了行驶路线;3)客户的期望需求影响了库存现金风险。     

多无人机协同任务策略优化

从研究多无人机协同任务的系统资源分配、任务分配、航线规划、轨迹优化等问题入手,建立了多基地多无人机协同侦察模型.针对问题,首先利用"栅格化聚拢"的思想对目标点进行过滤优化,进而对目标群和无人机基地进行了任务分配,而后结合蚁群算法、贪心算法、最短路径算法等思想,通过Matlab平台,计算出能够让无人机停留在雷达探测区域总时间最少的最优策略.     

A memetic algorithm for the multiperiod vehicle routing problem with profit

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.     

Heuristic,meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation

The allocation of fresh produce to shelf space represents a new decision support research area which is motivated by the desire of many retailers to improve their service due to the increasing demand for fresh food. However, automated decision making for fresh produce allocation is challenging because of the very short lifetime of fresh products. This paper considers a recently proposed practical model for the problem which is motivated by our collaboration with Tesco. Moreover, the paper investigates heuristic and meta-heuristic approaches as alternatives for the generalized reduced gradient algorithm, which becomes inefficient when the problem size becomes larger. A simpler single-item inventory problem is firstly studied and solved by a polynomial time bounded procedure. Several dynamic greedy heuristics are then developed for the multi-item problem based on the procedure for the single-item inventory problem. Experimental results show that these greedy heuristics are much more efficient and provide competitive results when compared to those of a multi-start generalized reduced gradient algorithm. In order to further improve the solution, we investigated simulated annealing, a greedy randomized adaptive search procedure and three types of hyper-heuristics. Their performance is tested and compared on a set of problem instances which are made publicly available for the research community.