考虑交通拥堵规避的低碳时变车辆路径问题研究

针对时变路网条件下的低碳车辆路径问题,首先,分析车辆离散行驶速度与连续行驶时间之间的关系,依据“先进先出”准则设计基于时间段划分的路段行驶时间计算方法,引入考虑车辆速度、实时载重、行驶距离与道路坡度因素的碳排放计算函数;然后,在此基础上以所有车辆的碳排放量最小为目标构建低碳时变车辆路径问题数学模型;最后,引入交通拥堵指数,设计交通拥堵规避方法,并根据模型特点设计一种改进蚁群算法求解.实验结果表明,所提出方法能有效规避交通拥堵、缩短车辆行驶时间、减少车辆碳排放,促进物流配送与生态环境和谐发展.     

Ride sharing with flexible participants: a metaheuristic approach for large‐scale problems

Severe traffic congestion and growing ecological consciousness have led to the rise of alternative transportation systems. Ride sharing is one such alternative in which drivers and passengers with similar time schedules and travel plans are matched. For this service to be effective, a large number of users are required to increase the probability of finding suitable travel partners. The present paper proposes a late acceptance metaheuristic to decide which users act as drivers and to construct their routes. The underlying optimization model allows passengers to walk to/from alternative pickup/drop‐off locations so as to further exploit user flexibility. A computational study quantifies the impact of different types of participant flexibility on CO₂ emissions. These insights can inform and support policymakers in organizing effective ride‐sharing systems.     

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 multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-To-Order environment,considering order priority

Nowadays, mixed-model assembly line is used increasingly as a result of customers’ demand diversification. An important problem in this field is determining the sequence of products for entering the line. Before determining the best sequence of products, a new procedure is introduced to choose important orders for entering the shop floor. Thus the orders are sorted using an analytical hierarchy process (AHP) approach based on three criteria: critical ratio of each order (CR_o), Significance degree of customer and innovation in a product, while the last one is presented for the first time. In this research, six objective functions are presented: minimizing total utility work cost, total setup cost and total production rate variation cost are the objectives which were presented previously, another objective is minimizing total idle cost, meanwhile two other new objectives regarding minimizing total operator error cost and total tardiness cost are presented for the first time. The total tardiness cost tries to choose a sequence of products that minimizes the tardiness cost for customers with high priority. First, to check the feasibility of the model, GAMS software is used. In this case, GAMS software could not search all of the solution space, so it is tried in two stages and because this problem is NP-hard, particle swarm optimization (PSO) and simulated annealing (SA) algorithms are used. For small sized problems, to compare exact method with proposed algorithms, the problem must be solved using meta-heuristic algorithms in two stages as GAMS software, whereas for large sized problems, the problem can be solved in two ways (one stage and two stages) by using proposed algorithms; the computational results and pairwise comparisons (based on sign test) show GAMS is a proper software to solve small sized problems, whereas for a large sized problem the objective function is better when solved in one stage than two stages; therefore it is proposed to solve the problem in one stage for large sized problems. Also PSO algorithm is better than SA algorithm based on objective function and pairwise comparisons.     

Modelling household travel energy consumption and CO2 emissions based on the spatial form of neighborhoods and streets: A case study of Jinan,China

This paper presents a direct modelling approach to evaluate household travel energy consumption and CO₂ emissions based on the spatial form of neighborhoods and streets. It integrates one multinomial logit model and four double hurdle models to predict travel outcomes: vehicle ownership portfolio choice, car travel distance, bus travel distance, motorcycle travel distance and ebike travel distance. The energy consumption and CO₂ emissions are then estimated using these travel outcomes. A full application of the modelling approach is demonstrated through a pilot project in Jinan, China. A holdout validation is also performed to address the over-fitting problem of models calibrated from the training set data. Results show that the proposed approach is operational and appropriate for sketch planning applications to promote clean energy and low carbon city planning in urbanizing China.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

Hyperpath-based vehicle routing and scheduling method in time-varying networks for airport shuttle service

It is very significant for a reasonable vehicle routing and scheduling in city airport shuttle service to decrease operational costs and increase passenger satisfaction. Most of the existing reports for such problems assumed that the travel time was invariable. However, the ever-increasing traffic congestion often makes it variable. In this study, considering the time-varying networks, a vehicle routing and scheduling method is proposed, where the time-varying feature enables the traveler to select a direction among all the Pareto-optimal paths at each node in response to the knowledge of the time window demands. Such Pareto-optimal paths are referred to hyperpaths herein. To obtain the hyperpaths, an exact algorithm is designed in this study for addressing the bi-criteria shortest paths problem, where the travel time comes to be discontinuous time-varying. Given the techniques that generate all Pareto-optimal solutions exhibiting exponential worst-case computational complexity, embedded in the exact algorithm, a computationally efficient bound strategy is reported on the basis of passenger locations, pickup time windows and arrival time windows. As such, the vehicle routing and scheduling problem viewed as an arc selection model can be solved by a proposed heuristic algorithm combined with a dynamic programming method. A series of experiments by using the practical pickup data indicate that the proposed methods can obtain cost-saving schedules under the condition of time-varying travel times.

     

Data-driven approaches for emissions-minimized paths in urban areas

Concerns about air quality and global warming have led to numerous initiatives to reduce emissions. In general, emissions are proportional to the amount of fuel consumed, and the amount of fuel consumed is a function of speed, distance, acceleration, and weight of the vehicle. In urban areas, vehicles must often travel at the speed of traffic, and congestion can impact this speed particularly at certain times of day. Further, for any given time of day, the observations of speeds on an arc can exhibit significant variability. Because of the nonlinearity of emissions curves, optimizing emissions in an urban area requires explicit consideration of the variability in the speed of traffic on arcs in the network. We introduce a shortest path algorithm that incorporates sampling to both account for variability in travel speeds and to estimate arrival time distributions at nodes on a path. We also suggest a method for transforming speed data into time-dependent emissions values thus converting the problem into a time-dependent, but deterministic shortest path problem. Our results demonstrate the effectiveness of the proposed approaches in reducing emissions relative to the use of minimum distance and time-dependent paths. In this paper, we also identify some of the challenges associated with using large data sets.     

Multicriteria pickup and delivery problem with transfer opportunity

In this research, we develop a multiobjective vehicle routing and scheduling heuristic for a pickup and delivery problem. The problem contains time window, advanced request, multi-vehicle and many-to-many transport. In addition, the fleet size is not predetermined, and customers are allowed to transfer between vehicles. The objectives of scheduling are to minimize vehicle expense, tardiness and travel time. We propose a concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more than one customer to a vehicle at a time. It differs from the usual concurrent approach in three aspects: (i) it uses the look-ahead strategy to construct miniroute; (ii) it adopts the head/tail, head, and tail integration techniques; and (iii) it allows interactivity. The procedure takes full advantage of due time and travel time information and is implemented through a computer program. It is a one-phase heuristic that can be reiterated when necessary. We provide detailed programming procedures and present the computational results of the proposed algorithm through the real data.     

Solving a single-machine scheduling problem with maintenance,job deterioration and learning effect by simulated annealing

This paper presents a new nonlinear multi-objective mathematical model for a single-machine scheduling problem with three objectives: (1) minimizing the sum of the weighted jobs completion, (2) minimizing the sum of the weighted delay times, and (3) maximizing the sum of the job values in makespan. In addition, a number of constraints are incorporated in this presented model, such as repairing and maintenance periods, deterioration of jobs, and learning effect of the work process. Since this type of scheduling problem belongs to a class of NP-hard ones, its solution by common software packages is almost impossible, or at best very time consuming. Thus, a meta-heuristic algorithm based on simulated annealing (SA) is proposed to solve such a hard problem. At a final stage, the related results obtained by the proposed SA are compared with those results reported by the Lingo 8 software in order to demonstrate the efficiency and capability of our proposed SA algorithm.     

自动驾驶环境下交叉口车辆路径规划与最优控制模型

自动驾驶环境下的交叉口基于车车/车路之间的双向信息交互, 能保障自动驾驶车辆相互穿插与协作地通过交叉口, 而无需信号灯控制. 因此, 如何设计高效的面向自动驾驶车辆通行的交叉口管控模型, 已成为研究的热点. 已有研究在建模时, 均基于自动驾驶车辆在交叉口内部的行驶路径已知并作为模型输入, 且大多对交叉口内部的冲突点进行简化. 本文首先将交叉口空间离散化处理, 考虑车辆的实际尺寸并面向非常规交叉口, 使用椭圆曲线建立转弯车辆行驶路径的精确轨迹方程, 再通过外边界投影降维法建立轨迹方程和交叉口空间的映射关系. 建立了基于混合整数线性规划(Mixed integer linear programming, MILP)的自动驾驶交叉口管控模型, 以交叉口总延误最小为控制目标, 同时优化车辆在交叉口的最佳行驶路径和驶入时刻, 使用AMPL (A mathematical programming language)对模型进行编译并使用CPLEX求解器求解. 与经典感应控制和先到先服务模型进行对比, 结果表明, 本文所提出模型能对车辆进入交叉口的时刻和行驶路径进行双重优化, 显著降低自动驾驶车辆通过交叉口的车均延误, 提高交叉口空间的利用效率.     

A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times

This study considers a multi-trip split-delivery vehicle routing problem with soft time windows for daily inventory replenishment under stochastic travel times. Considering uncertainty in travel times for vehicle routing problems is beneficial because more robust schedules can be generated and unanticipated consequences can be reduced when schedules are implemented in reality. However, uncertainties in model parameters have rarely been addressed for the problems in this category mainly due to the high problem complexity. In this study, an innovative and practical approach is proposed to consider stochastic travel times in the planning process. In the planning model, the possible outcomes of vehicle arrivals and product delivery at retailers are systematically categorized and their associated penalty and reward are estimated. Thus, unanticipated costs for every scheduling decision can be incorporated into the planning model to generate vehicle routing schedules that are more robust facing uncertain traffic conditions. To solve the model that is characterized as an NP-hard problem in a reasonable amount of time, a two-stage heuristic solution algorithm is proposed. Finally, the stochastic model is compared with the deterministic model in both planning and simulated operation stages using the data of a supply chain in Taiwan. The result confirms that the schedule generated by the stochastic model is more robust than the one created with the deterministic model because undesired outcomes such as unfulfilled demands are greatly reduced.     

车路协同环境下基于动态车速的相位差优化模型

针对基于固定路段行驶车速的相位差优化模型在优化双向滤波时存在的不足,本文基于车路协同环境下车辆–信号控制系统双向、实时通信的运行环境,研究并建立了车辆动态速度与交叉口相位差的整合优化模型.首先,基于对上游交叉口流出的两类交通流,即饱和交通流和非饱和交通流运行特征分析,建立了速度与相位差相互影响关系模型,在此基础上,分别针对两种不同的交通流,以干道实时流量与速度乘积最大为目标,考虑初始排队清空时间,可变速度范围,和相位差取值空间等约束条件,建立了车辆速度与相位差的动态优化模型,从而实现干道交通流不停车通过量最大且延误最小的目的.最后,对比分析了本文模型与经典Maxband绿波优化模型及Synchro软件的信号协调控制优化方案,结果表明,相比其他两种典型优化方法,本文模型能显著提高双向绿波带宽并大幅减少停车次数,提高协调控制的效益.     

The CONTRAM Dynamic Traffic Assignment Model

CONTRAM is a computer model of time-varying traffic in road networks, which takes as input the network definition and time-varying demand for travel between a set of origin and destination zones, and outputs the resulting network flows, routes and travel times. It combines a macroscopic time-sliced traffic model with disaggregate dynamic assignment of traffic, so is intermediate between macroscopic equilibrium and microscopic models. The paper details the methods used, including time-dependent queuing which plays a central role, and the treatment of network definition, user classes, road capacities, signals and coordination, vehicle emissions, Intelligent Transport Systems and research lines.     

Scheduling rules for dynamic shops that manufacture multi-level jobs

The problem of scheduling in dynamic conventional jobshops has been extensively investigated over many years. However, the problem of scheduling in assembly jobshops (i.e. shops that manufacture multi-level jobs with components and subassemblies) has been relatively less investigated in spite of the fact that assembly jobshops are frequently encountered in real life. A survey of literature on dynamic assembly jobshop scheduling has revealed that the TWKR-RRP rule is the best one for minimizing the mean flowtime and staging delay, and the job due-date (JDD) rule is the best for minimizing the mean tardiness of jobs. However, the objectives of minimizing the maximum flowtime (and maximum staging delay) and standard deviation of flowtime (and standard deviation of staging delay) are as important as the minimization of mean flowtime and mean staging delay. Likewise, the objectives of minimizing the maximum tardiness and standard deviation of tardiness are also as important as the minimization of mean tardiness. The reason is that the maximum and standard deviation values of a performance measure indicate the worst-case performance of a dispatching rule. The present study seeks to develop efficient dispatching rules to minimize the maximum and standard deviation of flowtime and staging delay, and the maximum and the standard deviation of conditional tardiness of jobs. The dispatching rules are based on the computation of the earliest completion time of a job and consequently determining the latest finish time of operations on components/subassemblies of a job. An extensive simulation-based investigation of the performance evaluation of the existing dispatching rules and the proposed dispatching rules has been carried out by randomly generating jobs with different structures and different shop utilization levels. It has been found from the simulation study that the proposed rules are quite effective in minimizing the maximum and standard deviation of flowtime and staging delay, and the maximum conditional tardiness and standard deviation of conditional tardiness.     

考虑时变速度的多车场绿色车辆路径模型及优化算法

针对多车场绿色车辆路径问题,根据顾客的坐标位置,采用K-means聚类方法将顾客分配给不同的车场;考虑时变速度和实时载重对车辆油耗和碳排放的影响,确定车辆油耗和碳排放的度量函数;在此基础上,以车辆油耗成本、碳排放成本、车辆使用成本、驾驶员工资以及时间窗惩罚成本之和最小化作为优化目标,构建多车场绿色车辆路径模型,并根据模...     

Generation of optimal schedules for metro lines using model predictive control

This paper presents a new methodology for computation of optimal train schedules in metro lines using a linear-programming-based model predictive control formulation. The train traffic model is comprised of dynamic equations describing the evolution of train headways and train passenger loads along the metro line, considering the time variation of the passenger demand and all relevant safety and operational constraints for practical use of the generated schedule. The performance index is a weighted sum of convex piecewise-linear functions for directly or indirectly modelling the waiting time of passengers at stations, onboard passenger comfort, train trip duration and number of trains in service. The proposed methodology is computationally very efficient and can generate optimal schedules for a whole day operation as well as schedules for transition between two separate time periods with known schedules. The use and performance of the proposed methodology is illustrated by an application to a metro line similar to the North-South line of São Paulo Underground.     

Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for fighter aircrafts (jobs) on multiple tankers (machines) to minimize the total weighted tardiness. ARSP can be modeled as a parallel machine scheduling with ready times and due date-to-deadline window to minimize total weighted tardiness. ARSP assumes that the jobs have different ready times and a due date-to-deadline window between refueling due date and a deadline to return without refueling. In this paper, we first formulate the ARSP as a mixed integer programming model. The objective function is a piece-wise tardiness cost that takes into account due date-to-deadline windows and job priorities. Since ARSP is NP-hard, two heuristics are proposed to obtain solutions in reasonable computation times, namely (1) modified ATC rule (MATC), (2) a simulated annealing method (SA). The proposed heuristic algorithms are tested in terms of solution quality and CPU time through computational experiments with data randomly generated to represent aerial refueling operations of an in-theater air operation. Solutions provided by both algorithms were compared to optimal solutions for problems with up to 12 jobs and to each other for larger problems with up to 60 jobs. The results show that, MATC is more likely to outperform SA especially when the problem size increases, although it has significantly worse performance than SA in terms of deviation from optimal solution for small size problems. Moreover CPU time performance of MATC is significantly better than SA in both cases.     

The problem of trains formation and scheduling: Integer statements

This paper considers the problem of trains formation and routing in a railway network. Under given delivery orders at dispatch stations, it is required to form trains and define their schedules and routes to destination stations by minimizing the total weighted delivery time. We suggest integer statements of this problem that account constraints arising in practice.     

A water-flow algorithm for flexible flow shop scheduling with intermediate buffers

We investigate the flexible flow shop scheduling problem with limited or unlimited intermediate buffers. A common objective of the problem is to find a production schedule that minimizes the completion time of jobs. Other objectives that we also consider are minimizing the total weighted flow time of jobs and minimizing the total weighted tardiness time of jobs. We propose a water-flow algorithm to solve this scheduling problem. The algorithm is inspired by the hydrological cycle in meteorology and the erosion phenomenon in nature. In the algorithm, we combine the amount of precipitation and its falling force to form a flexible erosion capability. This helps the erosion process of the algorithm to focus on exploiting promising regions strongly. To initiate the algorithm, we use a constructive procedure to obtain a seed permutation. We also use an improvement procedure for constructing a complete schedule from a permutation that represents the sequence of jobs in the first stage of the scheduling problem. To evaluate the proposed algorithm, we use benchmark instances taken from the literature and randomly generated instances of the scheduling problem. The computational results demonstrate the efficacy of the algorithm. We have also obtained several improved solutions for the benchmark instances using the proposed algorithm. We further illustrate the algorithm’s capability for solving problems in practical applications by applying it to a maltose syrup production problem.