Search

Given a set of timetabled bus trips, transport companies are faced with the challenge of finding a feasible driver schedule that covers all trips and abides by various labor union regulations. The regulations are primarily concerned with providing sufficient breaks for the drivers during the day. Practical limitations in the city network enforce drivers to travel by cars between bus stops to have breaks. Transport companies have a limited number of cars, known as staff cars,which have to be returned to their respective depots at the end of the day. The simultaneous scheduling of drivers and staff cars for the drivers is known as the driver scheduling problem with staff cars (DSPSC). It is estimated that the DSPSC accounts for 60% of a bus company’s operational expense, and this paper proposes a column generation approach that attempts to minimize operational expense. The column generation framework iterates between a master problem, a subproblem for generating driver variables and a subproblem for generating staff car variables. The subproblem related to the drivers is formulated as a resource constrained shortest path problem, which is solved by a dynamic programming approach. Several heuristic branching strategies are explored to find integer solutions. The proposed methodology is tested on eight real-life instances from seven Northern European bus companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver and an adaptive large neighborhood search (ALNS) heuristic indicate that the column generation approach provides improved solutions for six instances and the average improvement is 1.45%.

The coarse-grained multicomputer parallel model (CGM for short) has been used for solving several classes of dynamic programming problems. In this paper, we propose a parallel algorithm on the CGM model, with p processors, for solving the optimal binary search tree problem (OBST problem), which is a polyadic non-serial dynamic programming problem. Firstly, we propose a dynamic graph model for solving the OBST problem and show that each instance of this problem corresponds to a one-to-all shortest path problem in this graph. Secondly, we propose a CGM parallel algorithm based on our dynamic graph to solve the OBST problem through one-to-all shortest paths in this graph. It uses our new technique of irregular partitioning of the dynamic graph to try to bring a solution to the well-known contradictory objectives of the minimization of the communication time and the load balancing of the processors in this type of graph. Our solution is based on Knuth’s sequential solution and required $${\mathcal {O}}\left( \dfrac{n^2}{p} \right)$$ time steps per processor and $$\lceil \sqrt{2p} \rceil + k \times \left( {\left\lceil \dfrac{\lceil \sqrt{2p} \rceil }{2} \right\rceil } + 1 \right)$$ communication rounds. Integer k is a parameter used in the partitioning technique of our algorithm. This new CGM algorithm performs better than the previously most efficient solution, which uses regular partitioning of the tasks graph.

Real-time vehicle guidance effectively reduces traffic jams and improves the operational efficiency of urban transportation. The trip time on a route is considered as a random process that changes with time, and the shortest path selection requires a random dynamic model and the solution of a decision-making problem. Thus, the shortest trip time is the criterion to determine the dynamic path selection by a random dynamic programming (DP) model which discretizes the trip times in the continuous segments on the route. In this study, a numerical model of random dynamic programming is established by using a probability tree model and an AND/OR (AO∗) algorithm to select the path of the shortest trip time. The results show that the branches of the probability tree are only accumulated on the “quantity” and do not cause a “qualitative” change. The inefficient accumulation of “quantity” affects the efficiency of the algorithm, so it is important to separate the accumulation of “quantity” from node expansion. The accumulation of “quantity” changes the trip time according to the entering time into a segment, which demands an improved AO∗ algorithm. The new AO∗ algorithm balances between efficiency and the trip time and provides the optimal real-time vehicle guidance on the road.

Several variants of the classical Constrained Shortest Path Problem have been presented in the literature so far. One of the most recent is the k-Color Shortest Path Problem ($$k$$ k -CSPP), that arises in the field of transmission networks design. The problem is formulated on a weighted edge-colored graph and the use of the colors as edge labels allows to take into account the matter of path reliability while optimizing its cost. In this work, we propose a dynamic programming algorithm and compare its performances with two solution approaches: a Branch and Bound technique proposed by the authors in their previous paper and the solution of the mathematical model obtained with CPLEX solver. The results gathered in the numerical validation evidenced how the dynamic programming algorithm vastly outperformed previous approaches.

We train an agent to navigate in 3D environments using a hierarchical strategy including a high-level graph based planner and a local policy. Our main contribution is a data driven learning based approach for planning under uncertainty in topological maps, requiring an estimate of shortest paths in valued graphs with a probabilistic structure. Whereas classical symbolic algorithms achieve optimal results on noise-less topologies, or optimal results in a probabilistic sense on graphs with probabilistic structure, we aim to show that machine learning can overcome missing information in the graph by taking into account rich high-dimensional node features, for instance visual information available at each location of the map. Compared to purely learned neural white box algorithms, we structure our neural model with an inductive bias for dynamic programming based shortest path algorithms, and we show that a particular parameterization of our neural model corresponds to the Bellman-Ford algorithm. By performing an empirical analysis of our method in simulated photo-realistic 3D environments, we demonstrate that the inclusion of visual features in the learned neural planner outperforms classical symbolic solutions for graph based planning., ECCV 2020

The shortest path problem is formulated as an $l_1$-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm. Although Dijkstra's algorithm and the LARS formulation provide exact solutions, they become impractical when the size of the graph is exceedingly large. To overcome this issue, the alternating direction method of multipliers (ADMM) is proposed to solve the lasso formulation. The resulting algorithm produces good and fast approximations of the shortest path by sacrificing exactness that may not be absolutely essential in many applications. Numerical experiments are provided to illustrate the performance of the proposed approach., 17 pages

In the literature on Network Optimization, k-splittable flows were introduced to enhance modeling accuracy in cases where an upper bound on the number of supporting paths for each commodity needs to be imposed, thus extending the suitability of network flow tools for an increased number of practical applications. Such modeling feature has recently been extended to dynamic flows with the introduction of the novel strongly NP-hard Quickest Multicommodity k-splittable Flow Problem (QMCkFP). Such a flows over time problem asks for routing and scheduling of each commodity demand through at most k different paths in a dynamic network with arc capacities per time step, while minimizing the time required by the overall process. In this work, we propose the first exact algorithm for solving the QMCkSFP. The developed technique falls within the Branch and Price class and is based on original relaxation, pricing and branching procedures. Linearization and variable substitution are used to obtain the relaxation problem from the path-based formulation of the QMCkSFP. The pricing problem is modeled as a Shortest Path Problem with Forbidden Paths with additional node-set resources on a time expansion of the original digraph and is solved via a tailored dynamic programming algorithm. Two branching rules are designed for restoring feasibility whenever k-splittable or binary variable domain constraints are violated. The results of an extensive batch of computational experiments conducted on small to medium-size reference instances are presented, showing a highly satisfactory performance of the proposed algorithm. The paper concludes with a discussion on further lines of research.

The cooperative control in complex multitasks using unmanned aerial vehicle and unmanned ground vehicle (UAV/UGV) is an important and challenging issue in the multirobot cooperative field. The main goal of the task studied in this paper is to minimize the time and energy consumed by the system to complete the assigned tasks. In this paper, a complex multitask problem using the hybrid UAV/UGV system is studied, which is divided into three stages, namely, the stage of finding the optimal locations of the relay stations for the UGV; the stage of solving the path planning problem for the UGV; and the stage of the task assignment for multi-UAVs. Furthermore, an improved integrated method is proposed to deal with the cooperative control problems in these three stages. Firstly, an adaptive clustering method is proposed to determine the locations of the UGV relay stations, and then an improved cuckoo search algorithm is used to find the shortest path for the UGV. Finally, a grouping method is presented to solve the multitask allocation problem of UAVs, based on an improved dynamic programming algorithm. In addition, some simulations are carried out and the results show that the proposed method has better performance when it comes to the time and energy consumption and can effectively guide the hybrid UAV/UGV system to carry out the complex multitasks.

The paper proposes a new real time motion generation technique for a mobile robot, which is able to find time-optimal motions along a curved path taking into account capabilities of the driving motors and ensuring the wheels rolling without skidding. The problem is converted to a time-optimal control of a second-order dynamic system under constraints on the control input, the first derivative of output, and mixed constraint on the control variable and the output derivative. After the state space discretization, the original problem is presented as a combinatorial one where the desired robot trajectory corresponds to a shortest path on the relevant graph. To find this path and ensure its real time implementation, a moving window strategy combined with dynamic programming is proposed. Advantages of this approach and its suitability to real time control are illustrated by a case study dealing the fastest motion of the mobile robot along a sinusoidal path.

International audience; The Resource Constrained Shortest Path Problem (RCSP P) models several applications in the fields of transportation and communications. The classical problem supposes that the resource consumptions and the costs are certain and looks for the cheapest feasible path. These parameters are however hardly known with precision in real applications, so that the deterministic solution is likely to be infeasible or suboptimal. We address this issue by considering a robust counterpart of the RCSP P. We focus here on resource variation and model its variability through the uncertainty set defined by Bertismas and Sim (2003,2004), which can model the risk aversion of the decision maker through a budget of uncertainty. We solve the resulting problem to optimality through the well-known three phase approach dealing with bounds computation, network reduction and gap closing. In particular, we compute robust bounds on the resource consumption and cost by solving the robust shortest path problem and the dual robust Lagrangian relaxation, respectively. Dynamic programming is used to close the duality gap. Upper and lower bounds are used to reduce the dimension of the network and incorporated in the dynamic programming in order to fathom unpromising states. An extensive computational phase is carried out in order to asses the behavior of the defined strategy comparing its performance with the state-of-the-art. The results highlight the effectiveness of our approach in solving to optimality * 1 benchmark instances for RCSP P when Γ is not too large, tailored for the robust counterpart. For larger values of Γ, we show that the most efficient method combines deterministic preprocesing with the iterative algorithm from Bertsimas and Sim (2003). We also illustrate the failure probability of the robust solutions through Monte Carlo sampling.

The paper presents a new motion generation technique for a mobile robot that is able to find time-optimal motions along a curved path that takes into account limitations of the driving motors and also ensures the wheels rolling without skidding. Mathematically, the problem is presented as a time-optimal control of a second order dynamic system under constraints on the control input, the first derivative of output, and also mixed constraint on the control variable and the output derivative. After the state space discretization, the original problem is converted into the combinatorial one where the desired robot trajectory is presented a shortest path on the relevant graph. To find this path and ensure its physical implementation, dynamic programming is applied that allows creating a set of feasible trajectories, the best one of which is selected at the final stage. Advantages of the proposed technique and its suitability of real-time control are illustrated by several examples dealing the mobile robot motion along the elliptic and star-type paths.

International audience; We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.

International audience; We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving time. Although optimal solutions may contain cycles and pseudo‐polynomially many arcs, we provide a representation of the solutions that is polynomial in the absolute value of the inverse of the slopes as well as in the dimensions of the graph. We further prove that the problem is NP‐Hard when the slopes are integer. We introduce a restriction of the problem where waits must be integer and propose pseudo‐polynomial algorithms for the latter. We also provide a pseudo‐FPTAS, polynomial in the ratio between the bound on the total waiting time and the minimum travel time. Finally, we discuss harder variants of the problem and show their inapproximability.

International audience; A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle performs a classical delivery tour, while the drones are constrained to perform back and forth trips. The objective is to minimize completion time. We propose an iterative two-step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and trips for the drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances confirm the efficiency of the approach and give some insights on this drone delivery system.

International audience; The paper proposes a technique for optimal motions generation in redundant robotic tape winding systems for manufacturing of high-pressure composite vessels. It also presents two industrial case studies dealing with the motion generation for basic types of winding lamina, helical and circumferential. The developed technique transforms the original continuous problem into a discrete one where the desired time-optimal motions are presented as a shortest path on the task graph satisfying the problem-specific acceleration and velocity constraints imposed on the joint coordinates. It allows generating the optimal trajectories using enhanced dynamic programming algorithm that considers both of these constraints. Efficiency of the developed technique is confirmed by simulation studies.

International audience; The paper proposes a methodology for optimal coordination of motions in robotic systems with multiple redundant actuators. In contrast to our previous results dealing with a single redundant axis, the extended technique is proposed allowing the robot, positioner and linear track to be actuated simultaneously in order to reduce the total processing time. The developed technique transforms the original continuous problem into a discrete one where the desired time-optimal motions are presented as a shortest path on the task graph satisfying the problem-specific acceleration and velocity constraints imposed on the joint coordinates. The desired time optimal motions are generated using enhanced dynamic programming algorithm that considers both of these constraints. Two case studies are presented to demonstrate efficiency of the approach and evaluate benefits of simultaneous actuation of all robotic system axes.

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.

Condition-based monitoring is used as part of predictive maintenance to collect real-time information on the healthy status of a vessel engine, which allows for a more accurate estimation of the remaining life of an engine or its parts, as well as providing a warning for a potential failure of an engine part. An engine failure results in delays and down-times in the voyage of a vessel, which translates into additional cost and penalties. This paper studies a spare part management problem for maintenance scheduling of a vessel operating on a given route that is defined by a sequence of port visits. When a warning on part failure is received, the problem decides when and to which port each part should be ordered, where the latter is also the location at which the maintenance operation would be performed. The paper describes a mathematical programming model of the problem, as well as a shortest path dynamic programming formulation for a single part which solves the problem in polynomial time complexity. Simulation results are presented in which the models are tested under different scenarios.

The knapsack problem (KP) is concerned with the selection of a subset of multiple items with known positive values and weights such that the total value of selected items is maximized and their total weight does not exceed capacity. Item values, item weights, and capacity are known in the deterministic case. We consider the stochastic KP (SKP) with stochastic item weights. We combine the formulation of the SKP with a probabilistic capacity constraint (CKP) and the SKP with simple recourse (SRKP). Capacity is made an integral part of the constraint set in terms of a chance constraint as in the CKP. The chance constraint allows for a violation of capacity, but the probability of a violation beyond an imposed limit is constrained. The capacity constraint is also included in the objective function in terms of a penalty function as in the SRKP. Penalty is an increasing function of the expected number of units of violation with proportionality as a special case. We formulate the SKP as a network problem and demonstrate that it can be solved by a label-setting dynamic programming approach for the Shortest Path Problem with Resource Constraint (SPPRC). We develop a dominance criterion for an elimination of states in the dynamic programming approach using only the deterministic value of items along with mean and variance of the stochastic weight of items corresponding to the associated paths in the underlying network. It is shown that a lower bound for the impact of potential extensions of paths is available as an additional means to limit the number of states provided the penalty cost of expected overtime is convex. Our findings are documented in terms of a computational study.

In this paper, we study the deterministic single-reservoir Hydro Unit Commitment Problem. Under some hypotheses, we present a time expanded graph representation for the problem, where, at each time step, nodes correspond to discrete operational points, and arcs refer to possible state changes. We show that our problem reduces to a Constrained Shortest Path Problem, propose and compare different approaches to solve the HUCP, based on mixed integer linear or dynamic programming.

We consider the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP), a routing problem where customers may request multiple commodities. The vehicles can deliver any set of commodities and multiple visits to a customer are allowed only if the customer requests multiple commodities. If the customer is visited more than once, the different vehicles will deliver different sets of commodities. Allowing the splitting of the demand of a customer only for different commodities may be more costly than allowing also the splitting of each individual commodity, but at the same time it is easier to organize and more acceptable to customers. We model the C-SDVRP by means of a set partitioning formulation and present a branch-price-and-cut algorithm. In the pricing phase, the ng-path relaxation of a constrained elementary shortest path problem is solved with a label setting dynamic programming algorithm. Capacity cuts are added in order to strengthen the lower bound. We solve to optimality within 2h instances with up to 40 customers and 3 commodities per customer. HighlightsWe address the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP).We design an efficient branch-price-and-cut algorithm to solve the problem to optimality.We solve to optimality within 2h instances with up to 40 customers and 3 commodities per customer.

Power management in multi-source hybrid electric vehicles (HEVs) is a nontrivial problem dealing with different forms of energy. Optimal-based approaches are not facile to apply in realtime due to their high computational requirements. Rule-based (RB) algorithms are suitable for realtime control; however, the solution provided is non-optimal. Development of applicable optimal-based solution in realtime control can ensure higher efficiency of HEVs. This paper presents a new method for realtime optimal control of multisource HEVs using adaptive dynamic programming (ADP). The developed concept is based on drive state recognition in terms of physics-based parameters. Vehicle operating conditions are offline optimized for each state using NSGA-II optimization tool. The optimized solution can be applied state-wise in realtime using adaptive RB method. To apply ADP, probabilistic drive state model is developed to provide a lookahead window and generate state transition network for the specified horizon. The algorithm is customized in terms of prediction stepsize/length to solve the shortest path problem in realtime. Experimental application is conducted using emulation test-rig to validate the results. Both simulation and experimental results show reduction of total cost function in terms of fuel consumption and on-board charge sustaining.Copyright © 2017 by ASME

The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This article presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a Hybrid Genetic Search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored by means of bi-directional dynamic programming, sequence concatenations, by using appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale ones. Recommendations on promising algorithm choices are provided relatively to average cluster size., Working Paper, MIT -- 22 pages

We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is NP-hard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim 2003 and their extension to variable uncertainty by Poss 2013. We apply classical techniques to show that the problem with capacity constraints can be solved in pseudopolynomial time. However, we prove that the problem with time windows is NP-hard in the strong sense when NP is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudopolynomial when NP is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 662, 98-111 2015

When the future wind direction is uncertain, the tactical decisions of a yacht skipper involve a stochastic routing problem. The objective of this problem is to maximise the probability of reaching the next mark ahead of all the other competitors. This paper describes some numerical experiments that explore the effect of the skipper's risk attitude on their policy when match racing another boat. The tidal current at any location is assumed to be negligible, while the wind direction is modelled by a Markov chain. Boat performance in different wind conditions is defined by the output of a velocity prediction program, and we assume a known speed loss for tacking and gybing. We compare strategies that minimise the average time to sail the leg with those that seek to maximise the probability of winning, and show that by adopting different attitudes to risk when leading or trailing the competitor, a skipper can improve their chances of winning.

We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for $$d \in \{3, 4, 5\}$$ , whose Hanan grids contain up to several millions of edges.

In this paper we consider a label-setting dynamic-programming algorithm for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). We use a pseudo resource to guarantee that labels are permanent. We observe that storing the states based on the subset of nodes visited by the associated path can improve the performance of the algorithm significantly. To this end we use a variant of a prefix tree to store the states and show by computational experiments that the performance of the dynamic programming algorithm is improved significantly when the number of undominated states is large.

This paper presents our program in B-Prolog submitted to the third ASP solver competition for the Sokoban problem. This program, based on dynamic programming, treats Sokoban as a generalized shortest path problem. It divides a problem into independent subproblems and uses mode-directed tabling to store subproblems and their answers. This program is very simple but quite efficient. Without use of any sophisticated domain knowledge, it easily solves 14 of the 15 instances used in the competition. We show that the approach can be easily applied to other optimization planning problems.

This paper considers the general capacity expansion path problem (GCEP) for the telecommunication operators. We investigate the polynomial equivalence between the GCEP problem and the constrained shortest path problem (CSP) and present a pseudopolynomial algorithm for the GCEP problem, no matter the graph is acyclic or not. Furthermore, we investigate two special versions of the GCEP problem. For the minimum number arc capacity expansion path problem (MN-CEP), we give a strongly polynomial algorithm based on the dynamic programming. For the minimum-cost capacity expansion shortest path problem (MCESP), we give a strongly polynomial algorithm by constructing a shortest paths network.

This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.

We consider the problem of finding a control policy for a Markov Decision Process (MDP) to maximize the probability of reaching some states while avoiding some other states. This problem is motivated by applications in robotics, where such problems naturally arise when probabilistic models of robot motion are required to satisfy temporal logic task specifications. We transform this problem into a Stochastic Shortest Path (SSP) problem and develop a new approximate dynamic programming algorithm to solve it. This algorithm is of the actor-critic type and uses a least-square temporal difference learning method. It operates on sample paths of the system and optimizes the policy within a pre-specified class parameterized by a parsimonious set of parameters. We show its convergence to a policy corresponding to a stationary point in the parameters' space. Simulation results confirm the effectiveness of the proposed solution., Technical report accompanying an accepted paper to CDC 2011

In this paper we consider wireless cooperative multihop networks, where nodes that have decoded the message at the previous hop cooperate in the transmission toward the next hop, realizing a distributed space-time coding scheme. Our objective is finding optimal cooperator selection policies for arbitrary topologies with links affected by path loss and multipath fading. To this end, we model the network behavior through a suitable Markov chain and we formulate the cooperator selection process as a stochastic shortest path problem (SSP). Further, we reduce the complexity of the SSP through a novel pruning technique that, starting from the original problem, obtains a reduced Markov chain which is finally embedded into a solver based on focused real time dynamic programming (FRTDP). Our algorithm can find cooperator selection policies for large state spaces and has a bounded (and small) additional cost with respect to that of optimal solutions. Finally, for selected network topologies, we show results which are relevant to the design of practical network protocols and discuss the impact of the set of nodes that are allowed to cooperate at each hop, the optimization criterion and the maximum number of cooperating nodes.

IEEE International Conference on Systems, Man and Cybernetics -- OCT 10-13, 2010 -- Istanbul, TURKEY, WOS: 000295015300036, This paper reports work motivated by a real world assortment problem in packaging industry. A novel network flow model has been developed to solve the problem of selecting the optimal set of roll types for use in production. The model can incorporate fixed costs that depend on the number of elements in the assortment as well as the selected roll types. While the trade-off between inventory cost and cost of waste is resolved optimally through the model, graphical understanding of the trade-off can bring insights into the decision making process. This graphical analysis has been demonstrated on a computational example., IEEE

20 pages; International audience; The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection. Several attributes can be defined for one arc (travel time, travel cost . . . ), but the shortest route modelled by this arc is computed according to one single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. In this work, we propose to represent the road network with a multigraph, so that these alternative routes are considered, and to evaluate how it impacts on solution algorithms and solution values. A simple insertion algorithm is proposed and illustrated in the context of a on-demand transportation system developed in a French area. Computational experiments on academic and realistic data underline the potential cost savings brought by the multigraph model.

Shortest path problems appear as subproblems in numerous optimization problems. In most papers concerning multiple objective shortest path problems, additivity of the objective is a de-facto assumption, but in many real-life situations objectives and criteria, can be non-additive. The purpose of this paper is to give a general framework for dominance tests for problems involving a number of non-additive criteria. These dominance tests can help eliminate paths in a dynamic programming framework when using multiple objectives. Results on real-life multi-objective problems containing non-additive criteria are reported. We show that in many cases the framework can be used to efficiently reduce the number of generated paths.

Stochastic shortest path (SSP) problems arise in a variety of discrete stochastic control contexts. An optimal solutions to such a problem is typically computed using the value function, which can be found by solving the corresponding dynamic programming equations. In the deterministic case, these equations can be often solved by the highly efficient label-setting methods (such as Dijkstra's and Dial's algorithms). In this paper we define and study a class of Multimode Stochastic Shortest Path problems and develop sufficient conditions for the applicability of label-setting methods. We illustrate our approach on a number of discrete stochastic control examples. We also discuss the relationship of SSPs with discretizations of static Hamilton-Jacobi equations and provide an alternative derivation for several fast (non-iterative) numerical methods for these PDEs., 20 pages; 7 figures; submitted to "Mathematics of Operations Research"; minor changes & restructuring in accordance with reviewers' suggestions

International audience; Stochastic Shortest Path problems (SSPs) can be efficiently dealt with by the Real-Time Dynamic Programming algorithm (RTDP). Yet, RTDP requires that a goal state is always reachable. This article presents an algorithm checking for goal reachability, especially in the complex case of an uncertain SSP where only a possible interval is known for each transition probability. This gives an analysis method for determining if SSP algorithms such as RTDP are applicable, even if the exact model is not known. As this is a time-consuming algorithm, we also present a simple process that often speeds it up dramatically. Yet, the main improvement still needed is to turn to a symbolic analysis in order to avoid a complete state-space enumeration.

We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield optimal design algorithms for fixed-rate and entropy-constrained scalar quantizers, multi-resolution scalar quantizers, multiple description scalar quantizers, and Wyner-Ziv scalar quantizers. The algorithm guarantees globally optimal solutions for fixed-rate and entropy-constrained scalar quantizers and constrained optima for the other coding scenarios. We derive the algorithm by demonstrating the connection between scalar quantization, histogram segmentation, and the shortest path problem in a certain directed acyclic graph.