车辆数目未知的带时间窗口的车辆路径混合遗传算法

研究带时间窗口的车辆路径问题(VRPTW),主要考虑车辆容量约束、时间窗口约束、最大距离等约束,且完成配送所需的车辆数目不确定,要求在车辆数目最少的条件下再使总的行驶路径最短.用基于邻域搜索的混合遗传算法求解该问题,该算法既具有遗传算法的全局搜索能力,又具有邻域搜索算法的局部搜索能力.在求解过程中,设计新的前置交叉算子进行遗传操作,然后进行互换和逆转等邻域操作.应用MATLAB语言编程进行模拟计算,结果表明该混合遗传算法明显增强了群体演化的质量,提高了算法收敛速度,较好地解决了早熟收敛问题.     

混合超启发式法求解大规模VRP的优化研究

车辆路径是一类NP(non-deteministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义.提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题.先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进...     

最大优势搜索法

在半景搜索法的基础上提出了一种特别适用于专家系统技术的搜索方法－－最大优势搜索法,该搜索方法避免了半景搜索法在观景阶段一次性获取所有“OR”类原始数据结点存在情况的盲目步骤,通过跟踪期望解的优势,以较高的求解效率获得问题的最佳解。     

集装箱船舶贝内配载和堆场装船顺序协调优化

针对集装箱船舶贝内配载和堆场装船顺序协调优化问题，以堆场贝位和船舶贝位翻箱次数之和最小为优化目标，考虑堆场装船要求和船舶适航性等多种约束条件，建立数学模型. 鉴于问题的NP特性，提出混合演化策略算法(HES)求解模型，设计二维实数编码，提出基于力矩平衡和逐列装载的解码方法. 基于三点交叉互换的重组算子，单点突变的变异算子和互换的局部搜索策略对算法进行改进. 通过计算证明，对不同规模算例，HES算法均能求解出较优的贝内配载方案和堆场装船顺序.HES 算法与传统演化策略算法(ES)、粒子群算法 (PSO)、基于规则的启发式算法(HA-MBSCC)进行对比，进一步验证了算法的优越性.     

带折扣的多阶段库存系统的优化算法

针对供应商提供数量折扣、需求率随时间变化、周期性检查并补充库存的多阶段库存控制策略，提出一种优化算法．该算法以各时段的累计需求为根节点建立搜索树，从而将带折扣的库存问题转化为典型的动态批量问题，运用动态规划法即可求解．利用该算法可以找出在计划时段内总成本最小的补充策略．用算例说明了该算法的有效性．     

数量折扣条件下的动态订货批量优化

为研究卖方提供数量折扣安排时，买方优化动态订货批量的决策问题，考虑多种产品、多折扣类型和买卖双方的能力约束，建立了该问题统一的非线性混合整数规划模型．利用禁忌搜索技术设计启发式算法对模型求解．算例的计算结果验证了模型和算法的有效性。     

求解广义最小生成树问题的元启发式算法

针对广义最小生成树问题,设计了2种改进的元启发式算法来求解：单亲遗传模拟退火算法和改进的禁忌搜索算法。通过综合遗传算法和模拟退火算法的优点,提出了单亲遗传和模拟退火的混合算法,并设计了自适应选择法和自适应基因重组操作;在改进的禁忌搜索算法中,通过在2种邻域进行搜索来避免陷入局部最优。数值实验验证了算法的有效性。     

A parallel algorithm for train rescheduling

One of the crucial factors in achieving a high punctuality in railway traffic systems, is the ability to effectively reschedule the trains when disturbances occur. The railway traffic rescheduling problem is a complex task to solve both from a practical and a computational perspective. Problems of practically relevant sizes have typically a very large search space, making them time-consuming to solve even for state-of-the-art optimization solvers. Though competitive algorithmic approaches are a widespread topic of research, not much research has been done to explore the opportunities and challenges in parallelizing them. This paper presents a parallel algorithm to efficiently solve the real-time railway rescheduling problem on a multi-core parallel architecture. We devised (1) an effective way to represent the solution space as a binary tree and (2) a novel sequential heuristic algorithm based on a depth-first search (DFS) strategy that quickly traverses the tree. Based on that, we designed a parallel algorithm for a multi-core architecture, which proved to be 10.5 times faster than the sequential algorithm even when run on a single processing core. When executed on a parallel machine with 8 cores, the speed further increased by a factor of 4.68 and every disturbance scenario in the considered case study was solved within 6 s. We conclude that for the problem under consideration, though a sequential DFS approach is fast in several disturbance scenarios, it is notably slower in many other disturbance scenarios. The parallel DFS approach that combines a DFS with simultaneous breadth-wise tree exploration, while being much faster on an average, is also consistently fast across all scenarios.     

Route design for last-in,first-out deliveries with backhauling

The retail route design problem extends the capacitated vehicle routing problem with time windows by introducing several operational constraints, including order loading and delivery restrictions (last-in, first-out), order-dependent vehicle capacity, material handling limits at the warehouse, backhauling, and driving time bounds. In this paper, the problem is modeled on a directed network for an application associated with a major grocery chain. Because the corresponding mixed-integer program proved too difficult to solve with commercial software for real instances, we developed a greedy randomized adaptive search procedure (GRASP) augmented with tabu search to provide solutions. Testing was done using data sets provided Kroger, the largest grocery chain in the US, and benchmarked against a previously developed column generation algorithm. The results showed that cost reductions of $4887 per day or 5.58% per day on average, compared to Kroger’s corresponding solutions.     

The impact of advance purchase deadlines on airline consumers’ search and purchase behaviors

Airlines frequently use advance purchase ticket deadlines to segment consumers. Few empirical studies have investigated how individuals respond to advance purchase deadlines and price uncertainties induced by these deadlines. We model the number of searches (and purchases) for specific search and departure dates using an instrumental variable approach that corrects for price endogeneity. Results show that search and purchase behaviors vary by search day of week, days from departure, lowest offered fares, variation in lowest offered fares across competitors, and market distance. After controlling for the presence of web bots, we find that the number of consumer searches increases just prior to an advance purchase deadline. This increase can be explained by consumers switching their desired departure dates by one or two days to avoid higher fares that occur immediately after an advance purchase deadline has passed. This reallocation of demand has significant practical implications for the airline industry because the majority of revenue management and scheduling decision support systems currently do not incorporate these behaviors.