An Effective Hybrid Heuristic Algorithm for the Hub Location Problems of Small-Scale Uncapacitated Hub-and-Spoke Network

The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs.This paper proposed a hybrid heuristic based on genetic algorithm (GA) to resolve the uncapacitated single allocation hub location problem with fixed cost (USAHLPFC), according to the upper bound of the ratio of the number of hubs to the number of nodes.Computational experiments were conducted using the Civil Aeronautics Board (CAB) data set.Results indicate that, applying the proposed heuristic, one can obtain the optimal solutions for all small-scaled problems very efficiently.A comparison between the proposed hybrid heuristic method and the GA presented by Topcuoglu et al.shows that the former outperforms the latter when the discount factor α is less.     

考虑异质性出行需求的主支线公交树网络优化设计

公交线网优化设计是指在一定的运行约束条件下,选择1组公交线路和相关频率以达到优化目标的设计过程,可以表示为一个优化问题。针对具有高异质性出行需求的主支线公交树网络,在考虑客流需求和运营约束的前提下,以用户和运营者的成本最小为目标,提出了1种多目标非线性混合整数优化模型。优化变量为候选线路服务频率。为求解这一模型,设计了1种基于改进的布谷鸟算法的高效元启发式方法。该方法包括初始候选路线集生成过程;基于MNL模型的公交分配过程;确定路线服务频率的改进布谷鸟算法过程。通过算例验证了该方法的有效性和适用性。数值分析结果表明,该算法通过对所有可能的候选路径的服务频率选择得到接近最优的公交线路网络。另一方面,通过保持高峰时的公交线路为有效备择线路,为具有异质性出行需求的网络的重新设计提供了更好的解决方案。此外,该系统在1次运行中产生了1组帕累托解,其允许公交线网设计师评估运营商成本和乘客成本并做出折中方案。通过比较3种算法的计算结果和CPU时间,证明了改进的布谷鸟算法的可靠性和有效性。另外还研究了最优公交网络设计与公交运行速度、总需求规模等关键设计输入参数之间的关系,分析结果表明,关键设计输入参数与最优公交网络具有一定的协同效应。模型与算法为实际的大规模主支线公交树网络的优化设计提供了1种有效的工具。     

A hybrid Genetic Algorithm approach to minimize the total joint cost of a single-vendor multi-customer integrated scheduling problem

This paper addresses the scheduling of supply chains with interrelated factories consisting of a single vendor and multiple customers. In this research, one transporter is available to deliver jobs from vendor to customers, and the jobs can be processed by batch. The problem studied in this paper focuses on a real-case scheduling problem of a multi-location hospital supplied with a central pharmacy. The objective of this work is to minimize the total cost, while satisfying the customer’s due dates constraints. A mathematical formulation of the problem is given as a Mixed Integer Programming model. Then, a Branch-and-Bound algorithm is proposed as an exact method for solving this problem, a greedy local search is developed as a heuristic approach, and a hybrid Genetic Algorithm is presented as a meta-heuristic. Computation experiments are conducted to highlight the performance of the proposed methods.     

A multi-period optimization model for the deployment of public electric vehicle charging stations on network

A multi-period multipath refueling location model is developed to expand public electric vehicle (EV) charging network to dynamically satisfy origin–destination (O–D) trips with the growth of EV market. The model captures the dynamics in the topological structure of network and determines the cost-effective station rollout scheme on both spatial and temporal dimensions. The multi-period location problem is formulated as a mixed integer linear program and solved by a heuristic based on genetic algorithm. The model and heuristic are justified using the benchmark Sioux Falls road network and implemented in a case study of South Carolina. The results indicate that the charging station rollout scheme is subject to a number of major factors, including geographic distributions of cities, vehicle range, and deviation choice, and is sensitive to the types of charging station sites.     

Modeling charging infrastructure impact on the electric vehicle market in China

The plug-in electric vehicle (PEV) is deemed as a critical technological revolution, and the governments are imposing various vehicle policies to promote its development. Meanwhile, the market success of PEVs depends on many aspects. This study integrates one’s use of charging infrastructure at home, public place and workplace into the market dynamics analysis tool, New Energy and Oil Consumption Credits (NEOCC) model, to systematically assess the charging infrastructure (home parking ratio, public charging opportunity, and charging costs) impact on PEV ownership costs and analyze how the PEV market shares may be affected by the attributes of the charging infrastructure. Compared to the charging infrastructure, the impact of battery costs is incontrovertibly decisive on PEV market shares, the charging infrastructure is still non-negligible in the PEV market dynamics. The simulation results find that the public charging infrastructure has more effectiveness on promoting the PEV sales in the PEV emerging market than it does in the PEV mature market. However, the improvement of charging infrastructure does not necessarily lead to a larger PEV market if the charging infrastructure incentives do not coordinate well with other PEV policies. Besides, the increase of public charging opportunities has limited motivations on the growth of public PEV fleets, which are highly correlated to the number of public fast charging stations or outlets. It also finds that more home parking spaces can stimulate more sales of personal plug-in hybrid electric vehicles instead of personal battery electric vehicles.     

Dynamic travel time prediction using data clustering and genetic programming

The current state-of-practice for predicting travel times assumes that the speeds along the various roadway segments remain constant over the duration of the trip. This approach produces large prediction errors, especially when the segment speeds vary temporally. In this paper, we develop a data clustering and genetic programming approach for modeling and predicting the expected, lower, and upper bounds of dynamic travel times along freeways. The models obtained from the genetic programming approach are algebraic expressions that provide insights into the spatiotemporal interactions. The use of an algebraic equation also means that the approach is computationally efficient and suitable for real-time applications. Our algorithm is tested on a 37-mile freeway section encompassing several bottlenecks. The prediction error is demonstrated to be significantly lower than that produced by the instantaneous algorithm and the historical average averaged over seven weekdays (p-value <0.0001). Specifically, the proposed algorithm achieves more than a 25% and 76% reduction in the prediction error over the instantaneous and historical average, respectively on congested days. When bagging is used in addition to the genetic programming, the results show that the mean width of the travel time interval is less than 5 min for the 60–80 min trip.     

A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time

Transit network timetabling aims at determining the departure time of each trip of all lines in order to facilitate passengers transferring either to or from a bus. In this paper, we consider a bus timetabling problem with stochastic travel times (BTP-STT). Slack time is added into timetable to mitigate the randomness in bus travel times. We then develop a stochastic integer programming model for the BTP-STT to minimize the total waiting time cost for three types of passengers (i.e., transferring passengers, boarding passengers and through passengers). The mathematical properties of the model are characterized. Due to its computational complexity, a genetic algorithm with local search (GALS) is designed to solve our proposed model (OPM). The numerical results based on a small bus network show that the timetable obtained from OPM reduces the total waiting time cost by an average of 9.5%, when it is tested in different scenarios. OPM is relatively effective if the ratio of the number of through passengers to the number of transferring passengers is not larger than a threshold (e.g., 10 in our case). In addition, we test different scale instances randomly generated in a practical setting to further verify the effectiveness of OPM and GALS. We also find that adding slack time into timetable greatly benefits transferring passengers by reducing the rate of transferring failure.     

Optimal road design through ecologically sensitive areas considering animal migration dynamics

With increasing land transportation requirements in both urban and rural areas, roads are encroaching ever more on animal habitats, where collisions with vehicles are a leading contributor to wildlife mortality. While road designers recognise the importance of accounting for such impacts at the design level, existing approaches simply either ignore viable habitat or avoid such regions entirely. Respectively, this can result in road alignments that are overly damaging to vulnerable species or prohibitively expensive to build and operate. The research presented in this paper investigates the effects of explicitly accounting for animal mortality on the design of a road through an ecologically sensitive area. The model presented achieves this by incorporating a spatially-explicit animal migration and road mortality model into an accepted optimal road alignment algorithm to propose low-cost roads that maintain the animal population above a minimum threshold by the end of a specified design horizon. The new method was applied to an example scenario to demonstrate the effect of setting a minimum required animal population on the road design. This model was able to consistently produce a road that met a minimum required species conservation benefit. This reflected a major improvement over the model that ignored animal habitats while only requiring a minor increase in construction and operating costs compared to the model that avoids habitat.     

遗传算法在高速公路路径计算中的应用

高速公路路网模型问题是一个十分重要的问题,各种路径的算法一直是高速公路路网模型中研究的重点.文中讨论了用遗传算法求解高速公路路网模型中路径的问题,详细介绍了路网模型的建立、遗传算法的设计和各种算子的选择;并通过仿真计算验证了用遗传算法解决路网模型中路径问题的可行性.     

单交叉口的模糊控制与优化

模糊交通控制技术的研究，在提高交叉口通行能力方面已取得了较多成果。但是除了效率，交通公平也非常重要。本文提出一种在考虑变通安全的前提下，兼顾效率与公平的单交叉口模糊控制模型。该模型包括两个子控制器：相序控制器根据各车道的交通紧急程度决定通行相位；时间控制器根据该相位所属各车道的交通需求程度决定通行时间。同时，设计了改进的遗传算法，用于高效获得理想的控制策略。仿真结果表明，即使基于经验确定该模型的控制策略，也比感应控制和Pappis模型更加高效与公平，优化模型则进一步提高了算法的性能。