低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。     

Improving routing and scheduling decisions at a distributor of industrial gasses

This paper investigates cyclical inventory replenishment for a company's regional distribution center that supplies, distributes, and manages inventory of carbon dioxide (_CO2)$({\mathrm{CO}}_2)$ at over 900 separate customer sites in Indiana. The company previously experienced high labor costs with excessive overtime and maintained a regular back-log of customers experiencing stockouts. To address these issues we implemented a three-phase heuristic for the cyclical inventory routing problem encountered at one of the company's distribution centers. This heuristic determines regular routes for each of three available delivery vehicles over a 12-day delivery horizon while improving four primary performance measures: delivery labor cost, stockouts, delivery regularity, and driver–customer familiarity. It does so by first determining three sets of cities (one for each delivery vehicle) that must be delivered to each day based on customer requirements. Second, the heuristic assigns the remaining customers in other cities to one of the three “backbone routes” determined in phase 1. And third, it balances customer deliveries on each daily route over the schedule horizon. Through our methodology, we were able to significantly reduce overtime, driving time, and labor costs while improving customer service.     

基于改进蚁群算法的低碳车辆路径问题研究

全球气候恶化危及人类生存环境,物流运输过程中产生的大量温室气体则是祸源之一。本文考虑带有碳排放约束的车辆路径问题（VRP）,以车辆行驶里程最短和碳排放量最小为目标,构建了多目标的VRP非线性规划模型。提出了一种改进的蚁群系统算法对该模型进行求解,算法在更新路径上的蚂蚁信息素时引入了混沌扰动机制,此举能降低算法运行时陷入局部最优解的概率并有效提高算法的适应性。同时,对启发因子、状态转移概率、信息素更新等环节进行了优化设计,提高了最优路径的搜索效率。最后,数值仿真实验证明了该算法的求解表现优于同类研究常用的遗传算法和禁忌搜索算法,具有较强的全局寻优能力。在灵敏性和有效性的保证下,本研究所设计的改进蚁群算法能够较好地处理低碳车辆路径问题（LCVRP）。     

Supply vessel planning under cost,environment and robustness considerations

Offshore oil and gas installations need reliable cargo deliveries. The vessels supplying these installations on a periodic basis are expensive and constitute a source of emissions of greenhouse gases. Incorporating vessel speed optimization into the supply vessel planning process may significantly reduce fuel consumption and hence emissions. In addition, speed optimization may yield cost reductions if the number of vessels used does not increase. A main uncertainty factor, especially in the winter season, is the weather conditions which impact sailing and service times. Cost minimization and the application of speed optimization strategies may have implications on the robustness of weekly supply vessel schedules since idle times in the schedules are reduced. We develop a simulation-optimization based methodology that considers costs, emissions and robustness in the generation of weekly supply vessel schedules. Results of analyses conducted on real instances show that robustness requirements may yield both increased emissions and costs in the winter season. However, depending on instance characteristics, different degrees of robustness can be incorporated with both costs and emissions reductions through speed optimization.     

Approximation schemes for Euclidean vehicle routing problems with time windows

The vehicle routing problem with time windows (VRPTW) is a variant of the classical vehicle routing problem. The paper considers two dimensional and one dimensional VRPTW, in which each demand must be serviced within the time window which is designated by its customer. In the two dimensional problem, each customer has the same unit demand. The paper gives a quasi-polynomial time approximation scheme and an asymptotic polynomial time approximation scheme for the two dimensional and one dimensional problems under the Euclidean setting, respectively. With reasonable vehicle speed requirements, our algorithms could generate the solutions whose the total route length is \((1 + O(\varepsilon ))\) times of that of the optimum solutions.     

突发性片堵塞下两车信息共享的加拿大旅行者问题

提出突发性片堵塞下两车信息共享的加拿大旅行者问题,即两车欲从起点出发去终点,在运输过程中会遭遇突发性片堵塞,若两车对堵塞信息都能有限预知且车辆间可以信息共享,如何制定路径选择策略使两车花费的总时间尽可能少。针对该问题,采用在线问题与竞争策略的理论和方法,建立突发性片堵塞下两车信息共享的在线路径选择模型,设计混合贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,以及所选路径是否经过信息预知点到片堵塞起始点的路段（预知路段）等策略不同情形的分析,证明混合贪婪策略竞争比。最后进行实例分析,验证模型和策略的有效性。     

考虑自取服务和门到门服务的电动汽车物流网络优化策略研究

在环境意识增长与政府政策支持的有利条件下,电动汽车在物流领域得以快速发展。为提高物流服务的效率,降低企业运营成本,文中研究了考虑顾客服务策略的电动物流汽车服务设施选址与配送路径问题。采取顾客自行取货与配送人员送货上门相结合的多样化服务策略,使得服务站点的建设成本、顾客点配送路径成本以及服务站点补货路径成本之和最小。建立了整数规划数学模型,允许配送车辆在服务过程中前往服务站点接受充电服务。其次,提出了基于改进节约算法和禁忌算法的混合启发式算法MCWSA-TS。随后,在小规模算例将CPLEX运算结果与MCWSA-TS进行对比,证明了算法的有效性。最后,采用多组算例探讨了顾客取货半径对运营成本的影响,并对分离配送策略与联合配送策略进行对比分析。实验结果表明,多样化服务策略有助于企业满足顾客取货时间和取货方式的个性化需求。同时,兼顾运营成本与顾客满意度,促进电动汽车参与的物流服务快速发展。     

Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery

Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This paper studies time dependent vehicle routing problems with simultaneous pickup and delivery (TD-VRPSPD). We formulate this problem as a mixed integer programming model, where the time step function is used to calculate the travel time. To efficiently solve this complex problem, we develop a hybrid algorithm that integrates both Ant Colony System (ACS) and Tabu Search (TS) algorithms. Our algorithm uses the pheromones, travel time and vehicle residual loading capacity as a factor structure according to the characteristics of TD-VRPSPD. In our computational experiments, 56 groups of benchmark instances are used to evaluate the performance of our hybrid algorithm. In addition, we compare the performance of our hybrid algorithm with those of individual ACS and TS algorithms. The computational results suggest that our hybrid algorithm outperform stand-alone ACS and the TS algorithms.     

Adaptation of some vehicle fleet mix heuristics

Standard models used for the combined vehicle routing and vehicle fleet composition problem use the same value for the unit running cost across vehicles. In practice such a parameter depends on several factors and particularly on the capacity of the vehicle. The purpose of this paper is to show simple modifications of some well known methods to allow for variable running costs; and also to assess the effect of neglecting such variability. Interesting numerical results, measured in terms of changes in total cost or/and fleet configuration, are found at no extra computational effort.     

The lean improvement of the chemical emissions of motor vehicles based on preference ranking: A PROMETHEE uncertainty analysis

The motor vehicle has provided mobility and individual freedom for millions of people. However, vehicles embody the dilemma of contemporary industrialisation in that the environmental costs of automobility are equally large. This non-country specific study undertakes a PROMETHEE-based preference ranking of a small set of motor vehicles based on constituents of their exhaust emissions. As a model of an interested party's preference ranking of the motor vehicles, the subsequent uncertainty (sensitivity) analysis considered here, relates to what minimal (lean) changes would be necessary to a vehicle's emissions so that their preference ranking is improved. For a particular manufacturer, it can identify the necessary engineering performance modifications to be made to improve their perceived consumer based ranking. This is compounded by a further consideration of different levels of importance conferred on the criteria (vehicle emissions) and analogous analyses undertaken. The visual elucidation of the results rankings and changes to criteria values, offers a clear presentation of the findings to the interested parties.     

Decision Support System of Truck Routing and Refueling: A Dual‐Objective Approach

The variable‐route vehicle‐refueling problem (VRVRP) is a variant of the network‐flow problem which seeks, for a vehicle traveling from origin s to destination d, both the route and the refueling policy (sequence of fuel stations to use between s and d) that jointly minimize the fuel cost of operating the vehicle. Commercial‐grade decision support systems that solve the VRVRP are widely used by motor carriers, but they provide heuristic solutions only. Exact methods are available from the academic side, but because they focus on minimizing costs, they tend to cut fuel costs in exchange for increased vehicle miles (which can increase fuel consumptions and pollutants emission). We propose a new approach to the VRVRP that allows carriers to jointly seek the two possibly conflicting goals; minimizing fuel cost and vehicle miles. Computational testing shows that our approach (i) outperforms the commercial software products in both goals, and (ii) finds solutions that require significantly less vehicle miles than those given by the exact method proposed in the academic literature, without incurring unacceptable increases in fuel cost.     

An investigation into the vehicle routing problem with time windows and link capacity constraints

In this work, we investigate a new, yet practical, variant of the vehicle routing problem called the vehicle routing problem with time windows and link capacity constraints (VRPTWLC). The problem considers new constraints imposed on road links with regard to vehicle passing tonnage, which is motivated by a business project with a Hong Kong transportation company that transports hazardous materials (hazmats) across the city and between Hong Kong and mainland China. In order to solve this computationally challenging problem, we develop a tabu search heuristic with an adaptive penalty mechanism (TSAP) to help manage the company's vehicle fleet. A new data set and its generation scheme are also presented to help validate our solutions. Extensive computational experiments are conducted, showing the effectiveness of the proposed solution approach.     

The Benefits and Costs of New Fuels and Engines for Light‐Duty Vehicles in the United States

Rising oil prices and concerns about energy security and climate change are spurring reconsideration of both automobile propulsion systems and the fuels that supply energy to them. In addition to the gasoline internal combustion engine, recent years have seen alternatives develop in the automotive marketplace. Currently, hybrid‐electric vehicles, advanced diesels, and flex‐fuel vehicles running on a high percentage mixture of ethanol and gasoline (E85) are appearing at auto shows and in driveways. We conduct a rigorous benefit‐cost analysis from both the private and societal perspective of the marginal benefits and costs of each technology—using the conventional gasoline engine as a baseline. The private perspective considers only those factors that influence the decisions of individual consumers, while the societal perspective accounts for environmental, energy, and congestion externalities as well. Our analysis illustrates that both hybrids and diesels show promise for particular light‐duty applications (sport utility vehicles and pickup trucks), but that vehicles running continuously on E85 consistently have greater costs than benefits. The results for diesels were particularly robust over a wide range of sensitivity analyses. The results from the societal analysis are qualitatively similar to the private analysis, demonstrating that the most relevant factors to the benefit‐cost calculations are the factors that drive the individual consumer's decision. We conclude with a brief discussion of marketplace and public policy trends that will both illustrate and influence the relative adoption of these alternative technologies in the United States in the coming decade.     

A heuristic algorithm for the period vehicle routing problem

In this paper we consider the period vehicle routing problem, which is the problem of designing routes for delivery vehicles to meet customer service level requirements (not all customers require delivery on every day in the period). A heuristic algorithm, based upon the daily vehicle routing algorithm of Fisher and Jaikumar, is presented and computational results are given for test problems drawn from the literature.     

Dynamic vehicle routing for online B2C delivery

Electronic commerce (EC) is increasingly popular in today's businesses. The business-to-consumer EC environment has voluminous, unpredictable, and dynamically changing customer orders. A major part of the delivery system of this environment is the dynamic vehicle routing (DVR) system. This study investigates several algorithms suitable for solving the DVR problem in business-to-consumer (B2C) EC environment. It designs the solution process into three phases: initial-routes formation, inter-routes improvement, and intra-route improvement. A computer program is created to demonstrate a system simulating vehicle routing process under the online B2C environment. The simulated system collects data for system performance indexes such as simulation time, travel distance, delivery time, and delay time. The results show that when orders are placed through the Internet in an online B2C environment, the Nearest algorithms can be used to find satisfactory routes during the first phase of a DVR delivery system. The three-phase solution process is proven to be significantly better in travel distance and delivery time than the conventional single-phase solution process.     

Social Optimal Location of Facilities with Fixed Servers,Stochastic Demand,and Congestion

We consider two capacity choice scenarios for the optimal location of facilities with fixed servers, stochastic demand, and congestion. Motivating applications include virtual call centers, consisting of geographically dispersed centers, walk‐in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems. The choice of locations for such facilities influences both the travel cost and waiting times of users. In contrast to most previous research, we explicitly embed both customer travel/connection and delay costs in the objective function and solve the location–allocation problem and choose facility capacities simultaneously. The choice of capacity for a facility that is viewed as a queueing system with Poisson arrivals and exponential service times could mean choosing a service rate for the servers (Scenario 1) or choosing the number of servers (Scenario 2). We express the optimal service rate in closed form in Scenario 1 and the (asymptotically) optimal number of servers in closed form in Scenario 2. This allows us to eliminate both the number of servers and the service rates from the optimization problems, leading to tractable mixed‐integer nonlinear programs. Our computational results show that both problems can be solved efficiently using a Lagrangian relaxation optimization procedure.     

Technology Choice and Capacity Portfolios under Emissions Regulation

We study the impact of emissions tax and emissions cap‐and‐trade regulation on a firm's technology choice and capacity decisions. We show that emissions price uncertainty under cap‐and‐trade results in greater expected profit than a constant emissions price under an emissions tax, which contradicts popular arguments that the greater uncertainty under cap‐and‐trade will erode value. We further show that two operational drivers underlie this result: (i) the firm's option not to operate, which effectively right‐censors the uncertain emissions price; and (ii) dispatch flexibility, which is the firm's ability to first deploy its most profitable capacity given the realized emissions price. In addition to these managerial insights, we also explore policy implications: the effect of emissions price level, and the effect of investment and production subsidies. Through an illustrative example, we show that production subsidies of higher investment and production cost technologies (such as carbon capture and storage technologies) have no effect on the firm's optimal total capacity when firms own a portfolio of both clean and dirty technologies, but that investment subsidies of these technologies increase the firm's total capacity, conditionally increasing expected emissions. A subsidy of a lower production cost technology, on the other hand, has no effect on the firm's optimal total capacity in multi‐technology portfolios, regardless of whether the subsidy is a production or investment subsidy.     

有模糊时间窗的车辆调度组合干扰管理研究

研究带有模糊时间窗的车辆调度组合干扰管理模型及其混合遗传算法.采用时间窗模糊化处理方法,定义客户满意度函数,根据干扰管理思想对车辆调度中组合性干扰事件进行分析,从配送路径、配送成本和客户满意度三个方面进行干扰辨识与度量,建立基于模糊时间窗的车辆调度组合干扰管理模型;构造模型求解的混合遗传算法,将最佳客户插入规则与遗传算法结合,同时在算法中嵌入模糊优化程序以处理问题的模糊特征;进行数值实验,实验结果验证了模型与算法的有效性.     

随机旅行时间局内车辆路径问题的模型及其算法

人们在生活中会经常遇到随机旅行时间的局内车辆路径问题,如现实物流配送中的交通堵塞现象.文章在Laporte等的研究基础上,提出了一个考虑堵塞点动态产生、一个个遇到,堵塞时间为随机变量的模型,并构造了求解该模型的算法.