Solution of the Dial-a-Ride Problem with multi-dimensional capacity constraints

The Dial‐a‐Ride Problem (DARP) consists of planning routes and schedules for picking up and delivering users within user‐specified time windows. Vehicles of a given fleet with limited capacity depart from and end at a common depot. The travel time of passengers cannot exceed a given multiple of the minimum ride time. Other constraints include vehicle capacity and vehicle route duration. In practice, scheduling is made more complicated by special user requirements and an inhomogeneous vehicle fleet. The transportation of elderly and handicapped people is an important example, as space for wheelchairs is limited and a lift is required. In this study, we present a modified insertion heuristic to solve the DARP with multi‐dimensional capacity constraints, and the performance of the proposed algorithm is tested in simulation. We show that the proposed methodology is effective when compared with the classic algorithms.     

The Dial-A-Ride Problem with Transfers

The Dial-A-Ride Problem with Transfers (DARPT) consists in defining a set of routes that satisfy transportation requests of users between a set of pickup points and a set of delivery points, in the presence of ride time constraints. Users may change vehicles during their trip. This change of vehicle, called a transfer, is made at specific locations called transfer points. Solving the DARPT involves modeling and algorithmic difficulties. In this paper we provide a solution method based on an Adaptive Large Neighborhood Search (ALNS) metaheuristic and explain how to check the feasibility of a request insertion. The method is evaluated on real-life and generated instances. Experiments show that savings due to transfers can be up to 8% on real-life instances.     

Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network

In transportation networks with stochastic and dynamic travel times, park-and-ride decisions are often made adaptively considering the realized state of traffic. That is, users continue driving towards their destination if the congestion level is low, but may consider taking transit when the congestion level is high. This adaptive behavior determines whether and where people park-and-ride. We propose to use a Markov decision process to model the problem of commuters’ adaptive park-and-ride choice behavior in a transportation network with time-dependent and stochastic link travel times. The model evaluates a routing policy by minimizing the expected cost of travel that leverages the online information about the travel time on outgoing links in making park-and-ride decisions. We provide a case study of park-and-ride facilities located on freeway I-394 in Twin Cities, Minnesota. The results show a significant improvement in the travel time by the use of park-and-ride during congested conditions. It also reveals the time of departure, the state of the traffic, and the location from where park-and-ride becomes an attractive option to the commuters. Finally, we show the benefit of using online routing in comparison to an offline routing algorithm.

     

The Hopfield neural network applied to the Quadratic Assignment Problem

The Hopfield neural network is proposed as a method for solving the Quadratic Assignment Problem. The study involves determining the relevant parameter constraints, and provides a comparison of the performance of the Hopfield model with that of a conventional approach.     

A Model for Locating Park-and-Ride Facilities on Urban Networks Based on Maximizing Flow Capture: A Case Study of Isfahan, Iran

Traffic congestion is one of the main problems in large cities for which several approaches have been proposed. Park-and-ride is one of the best approaches that can remove traffic from the traffic network. Park-and-ride facilities are an important part of urban mass transit systems, effectively extending the service area and attracting commuters and other people who may not otherwise have used mass transit. However, its efficiency depends on its location in the urban network. In this research, we focus on travel time of shortest paths instead of the distance criterion for computing network traffic and develop a model for finding the best location(s) for siting park-and-ride systems so as to minimize the network traffic. The model is formulated based on population points, potential sites for park-and-ride establishment, and several Central Business District (CBDs). Then we present a Genetic algorithm that has been proved to be efficient in solving large size problems. Finally, the proposed model is used to locate park-and-ride facilities in the city of Isfahan, Iran.     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

An Integrated Quay Crane Assignment and Scheduling Problem

As maritime container transport is developing rapidly, the need arises for efficient operations at container terminals. One of the most important determinants of container handling efficiency is the productivity of quay cranes, which are responsible for unloading and loading operations for container vessels. For this reason, the Quay Crane Assignment Problem (QCAP) and the Quay Crane Scheduling Problem (QCSP) have received increasing attention in the literature and the present paper deals with the integration of these interrelated problems. A formulation is developed for the Quay Crane Assignment and Scheduling Problem (QCASP), which accounts for crane positioning conditions and a Genetic Algorithm (GA) is developed to solve the QCASP. Both the model formulation and the solution methodology are presented in detail and computational analysis is conducted in order to evaluate the performance of the proposed GA. The results obtained from the GA are compared with the results from an exact technique, thus providing complete information about the performance of the heuristic in terms of solution quality.     

Cultural differences in conceptual models of ride comfort for high‐speed trains

This study focuses on an analysis of the difference in cultural experiences for similar services through analyzing the difference in conceptual models of ride comfort for passengers of KTX (Korea Train eXpress) and TGV (Train a Grand Vitesse). These trains operate with identical platforms; KTX was introduced by K‐TGV (Korea‐TGV) based on TGV (French high‐speed train). For the conceptual models of ride comfort, this study surveyed 200 KTX passengers on the Seoul‐‐Busan line (duration: 2 hours 30 minutes) and surveyed 150 France TGV passengers on the Paris‐‐Marseilles line (duration: 2 hours 40 minutes). The conceptual models of ride comfort were analyzed using structural equation modeling (SEM). In the results of the study, though there were differences in cultural environment (e.g., physical environment, body size, etc.) and cultural mentality (e.g., preference, unconscious rule, etc.), the models of ride comfort for both countries shared similar critical factors. However, there were significant differences in loading values of ride comfort for these critical factors. In particular, there were differences of 1.5 to 2 times between the two models regarding the subfactors seat factor and human fatigue factor. In conclusion, this study elicits that experience factor is the most influential on ride comfort, and cultural factors are applied as essential variables in ride comfort improvement. © 2009 Wiley Periodicals, Inc.     

一种求解多车辆合乘匹配问题的适应性算法

车辆合乘匹配问题是研究如何通过优化车辆路线及车辆一乘客匹配来搭乘尽量多的乘客的问题。目前国内 外的研究多存在模型单一、脱离实际、算法效率不高等问题。针对该问题,提出一种基于吸引粒子群算法的问题求解 方法。通过吸引粒子群算法进行多车辆问题向单车辆问题的转化,形成车辆同乘客之间的初次匹配。根据初次匹配 结果利用先验聚类的思想将初次匹配结果进行排序,寻找较优需求序列排序方式。最后,通过相应的匹配再优化策略 将需求序列进行再优化。对比实验表明,基于吸引粒子群算法的问题求解方式能以较高的搭乘成功率以及较低的花 费完成车辆合乘匹配问题。     

具有执行器容错的汽车主动悬架系统有限频率H∞控制

本文研究了一类具有执行器容错的主动悬架系统有限频率H_∞控制问题.运用广义的Kalman-Yakubovich-Popov(KYP)引理,设计了有限频率H_∞控制器.该控制器不仅能够最大程度地减少路面在4～8 Hz范围内对乘客的影响,还能够保证汽车的悬架行程和车轮的动静载之比在它们允许的范围内.因此所设计的有限频率H_∞控制器不仅能够保证汽车驾驶的舒适性还能够保证汽车驾驶的安全性.为了解决系统状态不完全可测的问题,本文采用了动态输出反馈控制器策略.除此之外,在控制器的设计过程中还考虑了主动悬架系统的参数不确定性以及执行器随机故障的现象.最后,本文基于四分之一汽车主动悬架系统验证了控制器的有效性.     

Towards privacy-driven design of a dynamic carpooling system

Dynamic carpooling (also known as instant or ad-hoc ridesharing) is a service that arranges one-time shared rides on very short notice. This type of carpooling generally makes use of three recent technological advances: (i) navigation devices to determine a driver’s route and arrange the shared ride; (ii) smartphones for a traveller to request a ride from wherever she happens to be; and (iii) social networks to establish trust between drivers and passengers. However, the mobiquitous environment in which dynamic carpooling is expected to operate raises several privacy issues. Among all the personal identifiable information, learning the location of an individual is one of the greatest threats against her privacy. For instance, the spatio-temporal data of an individual can be used to infer the location of her home and workplace, to trace her movements and habits, to learn information about her centre of interests or even to detect a change from her usual behaviour. Therefore, preserving location privacy is a major issue to be able to leverage the possibilities offered by dynamic carpooling. In this paper we use the principles of privacy-by-design to integrate the privacy aspect in the design of dynamic carpooling, henceforth increasing its public (and political) acceptability and trust.     

A framework for developing a daily activity and multimodal travel planner

There is a need to further explore ways to use Advanced Traveler Information Systems (ATIS) to encourage transit and ridesharing. One mechanism is to provide convenient travel itinerary information, not just for one trip, but for a day's travel. The formulation should consider time constraints, activity needs, real transit service parameters and the actual street system. Basic algorithmic development is needed to spur the private sector interest in such a product by demonstrating its utility. The activity travel planner will aid its user in planning his daily itinerary by arranging the sequence of stops, suggesting and possibly selecting stop locations, providing transit route and schedule information, and suggesting travel routes. This paper develops a framework for solving the Travel Itinerary Planning Problem (TIPP) which is a variant of the Traveling Salesman Problem (TSP). Implementation of the solution algorithm would be used to develop and test a prototype for an activity and travel planner.     

Prediction of future origin-destination matrix of air passengers by fratar and gravity models

This article presents the need to predict the future demand of the air traffic passengers for scheduled commercial airlines. To determine the passengers demand, we have proposed an algorithm for assigning the origin destination (OD) matrix of the passengers air traffic between different airports. In order to realize the problem, we assume two different circumstances. Firstly, we predicted the total air traffic passengers with the target year. Secondly, we distributed the air traffic passengers between airports according to geographic location using the gravity and fratar models. The effectiveness of proposed method was examined through an air transportation network in Sumatra island (in Indonesia) as a case study.     

求解二次指派问题的最优迭代最大最小蚂蚁算法

为提高二次指派问题的求解质量,设计了一个有效的最大最小蚂蚁求解算法。首先,运用最优迭代思想,让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值,增强每轮搜索的有效性;其次,采用加入新任务后目标值的增量作为启发式因子来引导状态转移,增加每步搜索的目的性;然后,应用多精英策略来进行信息素更新,增加解的多样性;并设计有效的双重变异技术来提高解的质量,提高算法的收敛速度;最后,应用QAPLIB数据集进行了大量实验,结果表明:该算法在二次指派问题的求解质量和稳定性上显著优于其他算法。     

Intelligent design of a dynamic machine layout in uncertain environment of flexible manufacturing systems

Since Facility Layout Problem (FLP) affects the total manufacturing cost significantly, it can be considered as a critical issue in the early stages of designing Flexible Manufacturing Systems (FMSs), particularly in volatile environments where uncertainty in product demands is inevitable. This paper proposes a new mathematical model by using the Quadratic Assignment Problem formulation for designing an optimal machine layout for each period of a dynamic machine layout problem in FMSs. The product demands are considered as independent normally distributed random variables with known Probability Density Function (PDF), which changes from period to period at random. In this model, the decision maker’s defined confidence level is also considered. The confidence level represents the decision maker’s attitude about uncertainty in product demands in such a way that it affects the results of the problem significantly. To validate the proposed model, two different size test problems are generated at random. Since the FLP, especially in multi-period case is a hard Combinatorial Optimization Problem (COP), Simulated Annealing (SA) meta-heuristic resolution approach programmed in Matlab is used to solve the mathematical model in a reasonable computational time. Finally, the computational results are evaluated statistically.     

蚁群优化算法及其应用

蚂蚁算法是由意大利学者M．Dorigo等人提出的一种新型的模拟进化算法。该算法首先应用于旅行商问题并获得了极大的成功，其后，又被用于求解指派问题、Job—shop调度问题、图着色问题和网络路由问题等。实践证明，蚂蚁算法是一种鲁棒性强、收敛性好、实用性广的优化算法，但同时也存在一些不足，如收敛速度慢和容易出现停滞现象等。     

Elementary landscape decomposition of the frequency assignment problem

The Frequency Assignment Problem (FAP) is an important problem that arises in the design of radio networks, when a channel has to be assigned to each transceiver of the network. This problem is a generalization of the graph coloring problem. In this paper we study a general version of the FAP that can include adjacent frequency constraints. Using concepts from landscapes’ theory, we prove that this general FAP can be expressed as a sum of two elementary landscapes. Further analysis also shows that some subclasses of the problem correspond to a single elementary landscape. This allows us to compute the kind of neighborhood information that is normally associated with elementary landscapes. We also provide a closed form formula for computing the autocorrelation coefficient for the general FAP, which can be useful as an a priori indicator of the performance of a local search method.     

Integer programming methods for large-scale practical classroom assignment problems

In this paper we present an integer programming method for solving the Classroom Assignment Problem in University Course Timetabling. We introduce a novel formulation of the problem which generalises existing models and maintains tractability even for large instances. The model is validated through computational results based on our experiences at the University of Auckland, and on instances from the 2007 International Timetabling Competition. We also expand upon existing results into the computational difficulty of room assignment problems.     

差分进化算法在模糊多资源约束联合补货模型中的应用

本文用三角模糊数表示不确定的资金约束,用梯形模糊数表示不确定的存储空间约束,构建了模糊规划联合补货模型,目标函数为最小化订货成本、库存持有成本和运输成本,决策变量为基本补充周期和每种产品的补充周期。通过对变异算子与选择操作进行变化,设计了改进的差分进化算法对模型进行求解,并通过实例证实了模型与算法的科学合理性。     

Multi-objective K-connected Deployment and Power Assignment in WSNs using a problem-specific constrained evolutionary algorithm based on decomposition

The K-connected Deployment and Power Assignment Problem (DPAP) in WSNs aims at deciding both the sensor locations and transmit power levels, for maximizing the network coverage and lifetime objectives under K-connectivity constraints, in a single run. Recently, it is shown that the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) is a strong enough tool for dealing with unconstraint real life problems (such as DPAP), emphasizing the importance of incorporating problem-specific knowledge for increasing its efficiency. In a constrained Multi-objective Optimization Problem (such as K-connected DPAP), the search space is divided into feasible and infeasible regions. Therefore, problem-specific operators are designed for MOEA/D to direct the search into optimal, feasible regions of the space. Namely, a DPAP-specific population initialization that seeds the initial solutions into promising regions, problem-specific genetic operators (i.e. M-tournament selection, adaptive crossover and mutation) for generating good, feasible solutions and a DPAP-specific Repair Heuristic (RH) that transforms an infeasible solution into a feasible one and maintains the MOEA/D’s efficiency simultaneously. Simulation results have shown the importance of each proposed operator and their interrelation, as well as the superiority of the DPAP-specific MOEA/D against the popular constrained NSGA-II in several WSN instances.