CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up

This paper addresses the vehicle routing problem with sequence-constrained delivery and pick-up (VRPDP). We propose a multi-phase constructive heuristic that clusters nodes based on proximity, orients them along a route using shrink-wrap algorithm and allots vehicles using generalized assignment procedure. We employ genetic algorithm for an intensive final search. Trials on a large number of test-problems have yielded encouraging results.     

A dynamic stochastic programming model for international portfolio management

We develop a multi-stage stochastic programming model for international portfolio management in a dynamic setting. We model uncertainty in asset prices and exchange rates in terms of scenario trees that reflect the empirical distributions implied by market data. The model takes a holistic view of the problem. It considers portfolio rebalancing decisions over multiple periods in accordance with the contingencies of the scenario tree. The solution jointly determines capital allocations to international markets, the selection of assets within each market, and appropriate currency hedging levels. We investigate the performance of alternative hedging strategies through extensive numerical tests with real market data. We show that appropriate selection of currency forward contracts materially reduces risk in international portfolios. We further find that multi-stage models consistently outperform single-stage models. Our results demonstrate that the stochastic programming framework provides a flexible and effective decision support tool for international portfolio management.     

A stochastic model for the direct and inverse problem of adhesive materials

This work deals with the generation of artificial data based on experimental data for adhesive materials and the application of this data to the inverse and the direct problem. In reality there are only a very limited number of experimental data available. Therefore, the prediction of material behaviour is difficult and a statistical analysis with a stochastic proved thesis is nearly impossible. In order to increase the number of tests a method of stochastic simulation based on time series analysis is applied. With artificial data an arbitrary number of data is available and the process of the parameter identification can be statistically analysed. Additionally, one example is shown, which adapts the analysed material parameter to the direct problem. The stochastic finite element method is used to take into account the distribution and deviation of the fracture strain. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Interactive procedure for a multiobjective stochastic discrete dynamic problem

Multiple objectives and dynamics characterize many sequential decision problems. In the paper we consider returns in partially ordered criteria space as a way of generalization of single criterion dynamic programming models to multiobjective case. In our problem evaluations of alternatives with respect to criteria are represented by distribution functions. Thus, the overall comparison of two alternatives is equivalent to the comparison of two vectors of probability distributions. We assume that the decision maker tries to find a solution preferred to all other solutions (the most preferred solution). In the paper a new interactive procedure for stochastic, dynamic multiple criteria decision making problem is proposed. The procedure consists of two steps. First, the Bellman principle is used to identify the set of efficient solutions. Next interactive approach is employed to find the most preferred solution. A numerical example and a real-world application are presented to illustrate the applicability of the proposed technique.     

A stochastic dynamic traveling salesman problem with hard time windows

Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.     

A dynamic vehicle routing problem with multiple delivery routes

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.     

An iterated local search algorithm for the single-vehicle cyclic inventory routing problem

The Single-Vehicle Cyclic Inventory Routing Problem (SV-CIRP) belongs to the class of Inventory Routing Problems (IRP) in which the supplier optimises both the distribution costs and the inventory costs at the customers. The goal of the SV-CIRP is to minimise both kinds of costs and to maximise the collected rewards, by selecting a subset of customers from a given set and determining the quantity to be delivered to each customer and the vehicle routes, while avoiding stockouts. A cyclic distribution plan should be developed for a single vehicle.     

动态异方差随机前沿模型的Bayesian推断

随机前沿模型中如果忽略单边干扰项的异质性(heterogeneity)往往导致错误的效率估计.从个体特征的影响和方差的时变性两方面对单边干扰项进行考虑,提出异方差动态随机前沿模型.利用Gibbs抽样方法对动态异方差随机前沿模型进行Bayesian分析.导出了模型参数的后验条件分布,对中小样本的模拟实验显示在最小后验均方误差准则下得到的参数估计值非常接近真值.对电力公司的实际数据进行分析显示对数无效率项的方差有一定的时变性.     

An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows

The dial-a-ride problem (DARP) is a widely studied theoretical challenge related to dispatching vehicles in demand-responsive transport services, in which customers contact a vehicle operator requesting to be carried from specified origins to specified destinations. An important subproblem arising in dynamic dial-a-ride services can be identified as the single-vehicle DARP, in which the goal is to determine the optimal route for a single vehicle with respect to a generalized objective function. The main result of this work is an adaptive insertion algorithm capable of producing optimal solutions for a time constrained version of this problem, which was first studied by Psaraftis in the early 1980s. The complexity of the algorithm is analyzed and evaluated by means of computational experiments, implying that a significant advantage of the proposed method can be identified as the possibility of controlling computational work smoothly, making the algorithm applicable to any problem size.     

A stochastic dynamic programming model for valuing exclusivity from encroachment in franchising

Valuing territorial exclusivity in franchising is difficult because of the uncertainty associated with variables such as future franchise sales and brand strength. We present a stochastic dynamic programming model to value the exclusivity option from the perspective of both the franchisor and the franchisee. When there is positive value to the franchisor of including the exclusivity option in the contract, and to the franchisee of purchasing this option, the likelihood of franchisor-franchisee encroachment-related conflict is reduced. We also discuss structural results and explain our results using a numerical example.     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

A matheuristic for the stochastic facility location problem

Journal of Heuristics - In this paper, we describe a matheuristic to solve the stochastic facility location problem which determines the location and size of storage facilities, the quantities of...     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem

In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially in the case of passenger transportation, it often leads to excessive passenger ride times as well. Therefore, time-dependent and stochastic influences on travel speeds are relevant for finding feasible and reliable solutions. This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP). The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning). The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.     

A stochastic production planning model with a dynamic chance constraint

This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t₁ such that t₁?[O, T]where T is the end of the planning period, then (i) produce nothing until t₁ and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t₁ and T. If t₁ is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory.     

Multi-stage portfolio selection problem with dynamic stochastic dominance constraints

We study the multi-stage portfolio selection problem where the utility function of an investor is ambiguous. The ambiguity is characterized by dynamic stochastic dominance constraints, which are able to capture the dynamics of the random return sequence during the investment process. We propose a multi-stage dynamic stochastic dominance constrained portfolio selection model, and use a mixed normal distribution with time-varying weights and the K-means clustering technique to generate a scenario tree for the transformation of the proposed model. Based on the scenario tree representation, we derive two linear programming approximation problems, using the sampling approach or the duality theory, which provide an upper bound approximation and a lower bound approximation for the original nonconvex problem. The upper bound is asymptotically tight with infinitely many samples. Numerical results illustrate the practicality and efficiency of the proposed new model and solution techniques.