基于神经网络的电子地图最优路径研究

现阶段电子地图的应用已经深入到各行各业,最优路径的查找及规划作为GIS的一个关键问题,成为研究的一个难点,本文提出一种基于Hopfield神经网络的方法来解决地图最优路径问题。以物流配送中的车辆路径最优化为例,先根据Hopfield神经网络模型研究基于Hopfield的最优路径算法,然后探讨和验证该算法的可行性、实用性,最后通过算例分析对该方法进行验证。     

强化学习在车辆路径问题中的研究综述

车辆路径问题是物流运输优化中的核心问题,目的是在满足顾客需求下得到一条最低成本的车辆路径规划。但随着物流运输规模的不断增大,车辆路径问题求解难度增加,并且对实时性要求也不断提高,已有的常规算法不再适应实际要求。近年来,基于强化学习算法开始成为求解车辆路径问题的重要方法,在简要回顾常规方法求解车辆路径问题的基础上,重点总结基于强化学习求解车辆路径问题的算法,并将算法按照基于动态规划、基于价值、基于策略的方式进行了分类;最后对该问题未来的研究进行了展望。     

双参卷积理论模型预测交通通行时间

随着城市经济的发展和人们生活节奏的加快,智慧交通领域针对出行时间的研究已经成为热点问题。出行前预估行程中的通行时间便于人们更合理地规划出行路径,基于时间状态特征的路径规划就是解决交通问题的重要手段之一。现有模型多关注于车辆到达时间或多结合于真实历史时间数据进行预测,对浮动车的运行状态、车速等是否对时间存在影响的问题研究较少。基于此现状,提出了一种基于状态特征的道路时间预测模型,在固定时段内,利用出租车载客与否情况对轨迹数据进行深度相关性分析,结合车辆行驶速度构建一个基于密度划分的双参卷积理论模型,用得到的最终速度值对通行时间进行计算。实验结果表明该模型算法与传统时间预测算法相比有更高的精确度和实用性,提高了人们对出行安排的合理化和层次化,对制定城市道路出行策略具有重要的意义。     

车辆路径优化问题及求解方法研究综述

车辆路径优化问题一直以来是物流研究领域的一个热点和难点.现实生活的许多问题都可看作是车辆路径问题(VRP),因此国内外学者近年来不断提出多种车辆路径优化问题及求解方法以解决愈加复杂的问题.为进一步理清国内外研究现状,对如半开放式VRP、多级VRP、多目标VRP、绿色VRP等车辆路径优化问题,进行了总结分析,然后对车辆路径求解方法进行了介绍,特别地是对元启发式算法进行了较为详细的综述.最后,面向车辆路径优化问题和求解方法在当前形势下面临的新挑战,展望了一些新研究方向,如多目标优化、多级配送网络、绿色VRP、新型交通工具VRP和算法的通用性.     

基于进化计算的洒水车路径优化问题的求解

在利用进化计算对容量限制弦路径车辆行驶问题（Capacitated Arc Routing Problem,CARP）进行研究的基础上,对其数学模型、可行化算子进行改进,以适应实际生活中洒水车车辆路径优化问题。针对此问题,设计了局部搜索（Local Search）算子,此算子在染色体进化中有着显著的作用。来自于现实生活中的某市政环卫部门的实验数据真实可靠。通过进化计算对数据的求解,不仅得到了满意的结果,而且证明了该算法的可靠性及稳定性。在把计算后得出的优化路径用于实际洒水车线路安排后,其环卫部门节约了一定的人力物力,取得了一定的经济效益。根据实验分析,该算法能有效求解一定规模的CARP,并且具有一定的实用价值。     

多时间窗车辆路径问题的混合蚁群算法

研究了多时间窗车辆路径问题,建立了多时间窗车辆路径问题的数学模型,并基于蚁群算法设计了一种混合蚁群算法对问题进行了求解。该算法首先利用基本蚁群算法求解,然后采用2-opt算法和元胞自动算法对结果进行优化,同时加入变异算子。实验结果表明该算法可以有效地求解多时间窗车辆路径问题。     

多车场满载车辆路径优化算法

针对多车场满载车辆路径问题(MDVRPFL),结合节约法提出了一种依次对车场、配送中心、用户进行循环调整直到最优的迭代算法.该算法具有使总费用随迭代次数逐渐降低的特点,其运算结果能同时得到最优车辆分配方案和车辆行驶路径.最后用该算法对不同规模的算例进行试验.试验结果表明,该算法对多车场车辆路径问题有效适用.     

改进蚁群算法求解有时间窗的物流配送路径问题

物流配送车辆路径优化问题已被证明是一个NP难题,很难得到最优解。应用蚁群算法对带时间窗的物流车辆路径优化问题进行了算法设计,建立了车辆路径优化问题的蚁群算法数学模型及解决方案。通过对蚁群算法的分析,提出了改进的蚁群算法,并结合实例对该算法进行测试和分析,检验其有效性,结果表明了改进蚁群算法的可行性,符合实际的需要。     

基于有时间窗车辆路径问题的混合蚁群算法

有时间窗的车辆路径问题是目前组合优化领域研究的热点问题,其归属于NP-hard问题.在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合蚁群算法.该算法通过在蚁群算法中引AA-interchange变异算子,增强了算法的局部搜索能力,避免了早熟现象.实验结果表明,该算法能有效解决有时间窗的车辆路径问题.     

基于实时交通信息的车辆路径问题研究

石油化工企业的物流配送越来越成为降低成本、提高效率的1个重要环节,而车辆路径问题是其中的基础性问题。面对各种不确定性,动态随机车辆路径问题越来越成为有价值的研究方向,其关键在于实时交通信息的利用。本文研究了基于实时交通信息的单配送中心、有时间窗口约束的车辆路径问题,建立了混合整数规划模型,提出了利用实时速度估计信息的动态调度策略,并设计了带插入规则的节约算法。通过对标准benchmark问题进行仿真,验证了策略和算法的有效性。     

Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem

The vehicle routing problem (VRP) has been addressed in many research papers. Only a few of them take time-dependent travel speeds into consideration. Moreover, most research related to the VRP aims to minimize total travel time or travel distance. In recent years, reducing carbon emissions has become an important issue. Therefore, fuel consumption is also an important index in the VRP. In this research a model is proposed for calculating total fuel consumption for the time-dependent vehicle routing problem (TDVRP) where speed and travel times are assumed to depend on the time of travel when planning vehicle routing. In the model, the fuel consumption not only takes loading weight into consideration but also satisfies the “non-passing” property, which is ignored in most TDVRP-related research papers. Then a simulated annealing (SA) algorithm is proposed for finding the vehicle routing with the lowest total fuel consumption. An experimental evaluation of the proposed method is performed. The results show that the proposed method provides a 24.61% improvement in fuel consumption over the method based on minimizing transportation time and a 22.69% improvement over the method based on minimizing transportation distances.     

A two-stage heuristic method for vehicle routing problem with split deliveries and pickups

The vehicle routing problem （VRP） is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups （VRPSPDP） is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.     

带软时间窗的开放式满载车辆路径问题研究

为满足某些生产制造企业的满载运输需求,针对运输任务对车辆具有独占性的特点,分析得到总运输费用的大小取决于车辆的空车行驶费用,在此基础上,将带软时间窗的开放式满载车辆路径问题转化为带软时间窗的多车场开放式车辆路径问题,在非对称图上建立了相应的数学模型,并设计了近邻粒子群算法对模型进行求解。设计算例对算法进行了验证,实验结果表明：该算法可以快速求得软时间窗的开放式满载车辆路径问题的满意解。     

带时间窗的中转联盟运输调度问题的混合算法研究

介绍中转联盟运输调度问题的优越性和重要研究意义,建立了带中转点的优化运输调度问题的数学模型,并构造了求解该模型的优化算法,算法针对城市货物运输的特点,首先结合sweep算法和saving算法确定需求点与中转点之间的分派,随后采用改进的蚁群算法对每个中转点的运输路线进行优化。实例计算表明,提出的模型和算法能够有效的求解中转联盟运输调度问题。     

基于改进遗传算法的车辆调度模型

随着运输网络复杂程度的不断增加,运输车辆会遇到车祸、拥堵等干扰,传统的车辆调度模型缺少对这种干扰风险的分析,无法建立较为准确的调度模型,造成调度车辆遇到干扰时,调度效率大幅降低。为了避免上述缺陷,提出了一种基于改进遗传算法的车辆路径调度算法,引入扬长避短的思想,对所有的车辆运输路径进行编码,并对所有的路径进行选择、交叉和变异运算,运用模拟退火算法提高算法的寻优性能,形成车辆的高效调度。实验结果表明,利用改进算法进行车辆调度,能够提高运输的效率,从而满足实际运输需求。     

中转联盟运输调度的遗传算法研究

介绍中转运输调度问题的优越性。在此基础上建立了优化确定运输调度问题中转点的数学模型,并构造了求解该模型的遗传算法,算法中针对城市货物运输的具体特点,采用较新的交叉算子。实例计算表明:文中提出的模型和算法能够有效地解决AVRP中转点的确定问题。     

Multi-depot vehicle routing problem: a one-stage approach

This paper introduces multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD) which is one important and useful variant of the traditional multi-depot vehicle routing problem (MDVRP) in the supply chain management and transportation studies. After modeling the MDVRPFD as a binary programming problem, we propose two solution methodologies: two-stage and one-stage approaches. The two-stage approach decomposes the MDVRPFD into two independent subproblems, assignment and routing, and solves them separately. In contrast, the one-stage approach integrates the assignment with the routing where there are two kinds of routing methods-draft routing and detail routing. Experimental results show that our new one-stage algorithm outperforms the published methods. Note to Practitioners-This work is based on several consultancy work that we have done for transportation companies in Hong Kong. The multi-depot vehicle routing problem (MDVRP) is one of the core optimization problems in transportation, logistics, and supply chain management, which minimizes the total travel distance (the major factor of total transportation cost) among a number of given depots. However, in real practice, the MDVRP is not reliable because of the assumption that there have unlimited number of vehicles available in each depot. In this paper, we propose a new useful variant of the MDVRP, namely multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD), to model the practicable cases in applications. Two-stage and one-stage solution algorithms are also proposed. The industry participators can apply our new one-stage algorithm to solve the MDVRPFD directly and efficiently. Moreover, our one-stage solution framework allows users to smoothly add new specified constraints or variants.     

基于分支定价算法的双层轿运车运输问题

整车物流中双层轿运车运输问题属于一类需要考虑乘用车装载(vehicle filling problem, VFP)及轿运车路径规划(vehicle routing problem, VRP)的组合优化问题,称此类问题为VFRP(vehicle filling and routing problem).由于VFP和VRP的问题复杂性均为NP完全问题(non-deterministic polynomial complete problem, NPC),且VFRP等组合优化问题模型的目标函数及约束往往具有非凸结构,使得该类问题的线性化处理、精确算法的设计及求解效率的提升一直是该领域的研究难点.对此,以轿运车使用成本最低为目标,构建双层轿运车的VFRP模型,在此基础上提出两种线性化方法并设计改进分支定价算法(branch-and-price algorithm)以求解:在分支定价算法的基础上,提出结合最为分数策略(most-infeasible-branching strategy)和强分支策略(strong-branching strategy)的分支策略,以及在分支过程中降低可行域维度的...     

基于城市道路网的最短路径分析解决方案

近年来GIS对网络分析功能的需求迅速增长．网络分析中的一个关键问题是最短路径问题，它作为许多领域中速择最优问题的基础，在交通网络分析系统中占有重要地位．由于最短路径分析常用于汽车导航系统以及各种城市应急系统(如l10报警、l19火警以及120急救系统)，本文针对城市道路网的特点，提出了一种实用、高效的最短路径分析解决方案．