车辆合乘问题的分布式复合变邻域搜索算法

针对长期车辆合乘问题(long-term carpooling problem,LTCPP),提出一种基于分布式的复合变邻域搜索算法,利用分布式计算的优势可快速求解出大规模用户的合乘匹配方案。首先构建带有时间窗约束和车容量约束的数学模型,建立成本计算的目标函数;然后按复合距离优先算法将所有用户分配到各合乘小组中,最终得到满足约束条件的初始合乘方案。通过对变邻域搜索算法进行分布式处理,使算法可以对初始合乘方案进行并行迭代优化计算,得到最终的合乘方案。实验结果表明,该算法在速度和大规模问题求解质量上具有明显的优势。     

基于随机森林与变邻域下降的车辆合乘求解

为了最大化用户满意度，长期车辆合乘问题（LTCPP）被建模为多目标优化问题。然后，根据历史合乘数据以及用户满意度信息，使用随机森林算法计算每个指标对用户满意度的重要性影响，并作为对应优化目标的权重，以避免人为设定权重因子对优化结果的影响。提出了一种求解LTCPP的变邻域下降（VND）算法，通过顺序地在多个邻域内搜索得到问题的最优解。实验结果表明，结合随机森林和VND算法能为LTCPP提供高质量的解决方案，且具有很高的时间效率。     

基于偏好矩阵遗传算法求解长期车辆合乘问题

针对长期车辆合乘问题（LTCPP）,提出带有偏好矩阵的遗传算法（PMGA）,将拥有私家车且目的地相同的用户群体分配到产生总花费最少的合乘小组。首先,建立计算基于全体用户费用成本的目标函数,构建以用户时间窗和车容量为约束的长期车辆合乘模型;然后,结合模型特点,在传统遗传算法（GA）的基础上,通过在交叉算子与变异算子中添加偏好矩阵记录并更新用户间的偏好信息来提高可行解的数量和质量。实验结果表明,在相同计算环境下,当用户数量小于200时,通过PMGA所获得的20个解中的最优解的值与最优化算法相同;而处理大规模的实例时,PMGA可以获得更高质量的解。所提算法可以明显提高长期车辆合乘问题的求解质量,在降低汽车尾气污染和减少交通拥挤等方面具有重要作用。     

求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法

针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与CVRP的离散优化;为了提高算法的全局搜索能力,根据有序编码特点构造3种共栖搜索算子,扩大搜索空间;同时,结合变邻域搜索算法设计客户点重置、交换和2-OPT三种局部搜索策略,以提高解方案质量.算例验证分析表明,所提算法能够有效地解决容量约束车辆路径问题,求解质量优于所对比算法,具有可靠的全局稳定性.     

基于客户分级及换乘的多车辆合乘问题算法研究

多车辆合乘匹配问题(MRMP)是物流领域和交通领域的一个重要问题,现有的多车辆合乘匹配算法是以解决基本的多车辆合乘问题为主.为了提高客户的搭乘率,提出了客户分等级并且带有换乘的多车辆合乘匹配算法.该算法以蚁群优化算法为核心,分为3步:寻找起点终点集合;蚁群寻优,并在单向蚁群的基础上提出双向蚁群算法;车辆路径微调.实验仿真显示该算法获得80％以上的搭乘率,同时双向蚁群比单向蚁群具有更强的寻优能力.所得结果表明,该算法可以有效地获得带有换乘的匹配路线.     

考虑匹配可行性的长期合乘问题建模与求解*

车辆合乘对于减少碳排放、停车位需求以及缓解交通压力具有重要意义。针对长期车辆合乘问题(LTCPP),构建了带有车容量和时间窗约束的多目标优化模型。该模型以最小化用户行驶总距离、用户合乘产生的额外驾驶时间、用户实际启程到达时间与用户期望时间的差距以及最大化匹配可行性为目标。LTCPP是聚类和路由问题的组合,基于该特点,提出了一种分布式聚类蚁群算法(DCAC)求解LTCPP。该算法在蚂蚁行进中基于启发式信息与偏好值产生合乘组,继而采用枚举方法确定用户的最佳行驶路径。最后,在Apache Spark分布式计算框架中进行分布式实现。实验结果表明,该算法能为LTCPP提供高质量的解,并且在处理大规模LTCPP问题上具有明显优势。     

改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题

为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型.针对模型特点,设计了改进的自适应大规模邻域搜索(improved adaptive large neighborhood search,IALNS)算法,提出新的删除、修复算子及动态阶段加速策略,分别针对大规模的静态算例与动态算例进行算法性能测试.结果表明,与无改进策略的IALNS(IALNS-ND)相比,静态问题中在相同的求解时间内75％的算例(12个算例中9个)IALNS得到的最小值和平均值优于IALNS-ND,动态问题中95％(60个算例中57个算例)的算例可以得到成本和时间均优于IALNS-ND的解;与三种算法——自适应大规模邻域搜索算法(ALNS)、大规模邻域搜索算法(LNS)以及变邻域搜索算法(VNS)相比,静态问题中所有算例IALNS获得的总成本的最小值和平均值均优于三个对比算法,动态问题中58％(60个算例中35个算例)的算例IALNS能够以少于三个对比算法1.5倍甚至10倍的时间获得更优的解.同时随着问题动态度的提高,IALNS的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性.     

求解PDPTW问题的快速LNS算法

提出了一种解决有时间窗口的装卸货问题（PDPTW）的快速大规模领域搜索（LNS）算法。该算法基于大规模邻域搜索理论和随机扰动思想,在第一阶段主要以减少车辆为目标,第二阶段对第一阶段得到的解优化总路程长度。该算法能在较短时间内显著提高初始解的质量．克服了单纯以车辆数目或以总路程长度为目标的算法所得到解的局限性。通过标准算例的测试和同禁忌搜索的比较表明,该算法在求解PDPTW问题时,在计算时间和优化整体目标上更具优势。     

求解无等待流水调度的基于禁忌搜索的混合算法

本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。     

有禁飞区的时间依赖型车辆与无人机协同配送路径优化

本文针对有禁飞区的时间依赖型车辆与无人机协同配送路径问题,综合考虑分时段禁飞的无人机禁飞区域、车辆行驶速度连续变化、车辆及无人机能耗等因素,以车辆派遣成本、车辆能耗成本、无人机能耗成本之和最小为目标建立优化模型.根据问题特征,设计遗传变邻域搜索算法对其进行求解.针对遗传算法易早熟、局部搜索能力较差等缺陷,将变邻域搜索算法与其结合以增强算法的局部搜索能力,引入自适应邻域搜索次数以增强对种群的搜索深度,采用精英保留策略不断改进最优解.通过多组算例验证了算法的有效性,并分析了配送模式、禁飞区数量、车辆行驶速度变化对配送方案的影响,结果表明禁飞区及车辆速度等因素在很大程度上影响物流配送成本.研究成果不仅丰富了车辆与无人机协同配送的场景,拓展了VRP问题的研究,也为物流企业制定配送方案提供了依据.     

网约拼车出行的乘客车辆匹配及路径优化

城市道路拥堵严重及共享理念的盛行带来了拼车出行的兴起。出行线路相似的乘客共乘一辆车,可提高座位利用率、节省费用、缓解交通压力。以带时间窗约束的无换乘多车辆静态拼车问题为研究背景,从车辆使用费、途中走行成本及到达时间窗惩罚成本3个方面建立乘客车辆匹配及路径优化的目标函数,以车辆容量、乘客出发及到达时间窗、路径无迂回、乘客车辆匹配无重叠等限制构建模型约束条件,采用演化策略算法求解问题,根据模型特征设计编码解码规则,解码结果可同时获得车辆乘客匹配关系和走行路径,采用交叉变异操作更新迭代个体种群,进而求得最优解。运用MATLAB求解算例验证了模型可行性及算法有效性,结果表明算法能快速响应静态拼车问题,在较短时间即可给出乘客车辆的先后匹配关系及车辆走行路径,拼车方案相比独自出行能节省更多成本。     

An artificial bee colony algorithm with variable neighborhood search and tabu list for long-term carpooling problem with time window

Carpooling is an effective sharing economy mode that can increase utilization ratio of vehicle and relieve traffic pressure in cities. A carpooling system needs to provide feasible car-sharing solution under the constraint on time window of each passenger. Moreover, fairness is important to a long-term car sharing problem. A person will not willing to share his/her car if he/she has more contribution than others. In this paper, a long-term carpooling problem with time window is investigated for a group of people with a common destination. In order to guarantee fairness, a person can be chosen as a driver only for a limited number of consecutive days. An artificial bee colony algorithm combining variable neighbor search and tabu list (ABC-VNSTL) are proposed. We designed five neighbor search strategies: one-swapping strategy, all-swapping strategy, moving strategy, passenger to driver strategy, and solution exchange strategy. The experiments results demonstrate that ABC-VNSTL can obtain better solution quality than other six algorithms in the literature. As the number of participants increases, the advantages of ABC-VNSTL increase. In addition, ABC-VNSTL algorithm is more efficient than the compared algorithms under the condition of achieving same solution quality.     

A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints

This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.     

Feasibility and issues for establishing network-based carpooling scheme

Traffic issue has become one of the most concerns for citizens in metropolis. It is extremely hard to find an available vehicle in hot region during the peak hour. Due to the supply–demand contradiction, the authority is still seeking effective and economical carpooling solutions for “Taxi taking dilemma” without adding more vehicles. This paper mainly focuses on building a network-based carpooling scheme by analyzing the feasibility and related issues. Firstly, we provide some fundamental analysis for taxi carpooling based on the real taxis’ GPS traces. By setting up a correspondence relationship between physical locations and the coordinates of map, a macro impression about the space and time distribution of get on points for Beijing taxis are illustrated. According to the prediction algorithm, both the original and estimated benefits of carpooling are shown quantitatively. Secondly, four different network-based sharing schemes are presented and compared. The conditions of successful route matching are qualitatively studied. By identifying the merits and weaknesses comprehensively, we propose a new hybrid carpooling scheme. The concerns relate with the interaction process and packet structuring are considered carefully. A novel perspective for distinguishing vehicle and pedestrian in software design is also pointed out.     

多目标同时取送货选址–路径问题的多起点变邻域搜索算法

为使同时取送货的选址–路径问题(LRPSPD)的总成本和各路径间最大长度差最小化, 建立同时考虑车辆 容量和行驶里程约束的LRPSPD双目标模型. 采用多蚁群算法构造多个以信息素为关联的初始解, 作为多目标变邻 域搜索算法搜索的多个起点, 构造四类邻域结构进行变邻域搜索, 并根据最新获得的最优邻域解更新蚂蚁信息素, 从而使蚁群算法产生的多个初始解间、以及初始解与变邻域搜索产生的解之间均存在正向影响关系. 用该算法求 得文献中4组共128个算例的近似Pareto解集, 结果证明了最小化路径间最大长度差目标对于节点及需求分布不集 中算例的重要意义. 以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的算例结果进行比较, 结果 表明算法可在极短的运行时间里求得权衡各目标的Pareto解, 并使最小总成本目标值具有竞争性.     

Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

Ambulance routing for disaster response with patient groups

We consider a routing problem for ambulances in a disaster response scenario, in which a large number of injured people require medical aid at the same time. The ambulances are used to carry medical personnel and patients. We distinguish two groups of patients: slightly injured people who can be assisted directly in the field, and seriously injured people who have to be brought to hospitals. Since ambulances represent a scarce resource in disaster situations, their efficient usage is of the utmost importance. Two mathematical formulations are proposed to obtain route plans that minimize the latest service completion time among the people waiting for help. Since disaster response calls for high-quality solutions within seconds, we also propose a large neighborhood search metaheuristic. This solution approach can be applied at high frequency to cope with the dynamics and uncertainties in a disaster situation. Our experiments show that the metaheuristic produces high quality solutions for a large number of test instances within very short response time. Hence, it fulfills the criteria for applicability in a disaster situation. Within the experiments, we also analyzed the effect of various structural parameters of a problem, like the number of ambulances, hospitals, and the type of patients, on both running time of the heuristic and quality of the solutions. This information can additionally be used to determine the required fleet size and hospital capacities in a disaster situation.     

The green vehicle routing problem: A heuristic based exact solution approach

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time.