The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of network interdiction and graph theory research and are relevant to several practical optimization problems. The two different connectivity metrics that we consider regard the number of maximal...
We consider a time‐dependent network with a continuous‐time variable, in which time constraints are imposed both on the arrival times and on the waiting times at the nodes. Under certain continuity assumptions, we prove the existence of optimal paths, and we show that the optimal value function is lower‐semicontinuous. We present an exact solution algorithm, which computes both the optimal value function...
This article considers the problem of finding a route and schedule for a vehicle starting from a depot, visiting a set of customers, and returning to the depot, in a time‐dependent network where the objective is to minimize the greenhouse gas emissions. In this formulation, the speeds of the vehicle as well as the routes chosen are decision variables subject to limits determined by the level of congestion...
We consider the problem of locating facilities of two types at nodesof a tree network. Customers may need just one type of service, or bothtypes; in the latter case, to minimize transportation costs, the customers visit facilities of both types in a single trip. Each facility incurs a fixed cost that depends on the type of the facility and the node where it is located. It is required to minimize the...
We consider the variant of the shortest path problem in which a given set of paths is forbidden to occur as a subpath in an optimal path. We establish that the most‐efficient algorithm for its solution, a dynamic programming algorithm, has polynomial time complexity; it had previously been conjectured that the algorithm has pseudo‐polynomial time complexity. Furthermore, we show that this algorithm...
In this article, we consider a variation of the vehicle routing problem arising in the optimization of waste management systems. Constraints imposing adequate level of service to the citizens and even workload among the drivers make the problem challenging and ask for the design of specialized algorithmic approaches. We propose an exact optimization algorithm, in which dynamic generation of rows and...
We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is 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...
We study a dynamic network game between an attacker and a user. The user wishes to find a shortest path between a pair of nodes in a directed network, and the attacker seeks to interdict a subset of arcs to maximize the user's shortest‐path cost. In contrast to most previous studies, the attacker can interdict arcs any time the user reaches a node in the network, and the user can respond by dynamically...
Minimum cost flow problems on infinite networks arise, for example, in infinite‐horizon sequential decision problems such as production planning. Strong duality for these problems was recently established for linear costs using an infinite‐dimensional Simplex algorithm. Here, we use a different approach to derive duality results for convex costs. We formulate the primal and dual problems in appropriately...
In this article, a problem of rational splitter installation in Fiber‐to‐the‐Home (FTTH) networks is considered. The most expensive and time consuming part of the FTTH deployment is trenching and other labor involved in cable installation. When cables are deployed, the operator can start to connect customers to the network. However, the process still requires expenditures for both passive (splitters)...
The multi‐budgeted matching problem (mBM) is a weighted matching problem with independent edge cost functions. For each cost function, a budget constraint requires the accumulated cost not to exceed a corresponding budget. We show that the mBM is strongly NP‐hard on paths with uniform edge weights and budgets by a reduction from 3‐SAT. Subsequently, we propose a dynamic program for series‐parallel...
A promising new delivery model involves the use of a delivery truck that collaborates with a drone to make deliveries. Effectively combining a truck and a drone gives rise to a new planning problem that is known as the traveling salesman problem with drone (TSP‐D). This paper presents exact solution approaches for the TSP‐D based on dynamic programming and provides an experimental comparison of these...
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...
Free space optical communications are becoming a mature technology to cope with the needs of high data rate payloads for future low‐earth orbiting observation satellites. However, they are strongly impacted by clouds. In this paper, we aim to find a network of optical ground stations maximizing the percentage of data acquired by a low‐earth orbiting satellite that can be transferred to the Earth,...
Bidirectional dynamic programming is an algorithm that searches for paths in a network from both the starting and the ending nodes that optimize a given objective function. In recent years, bidirectional dynamic programming has been shown to be an effective means for solving resource‐bounded shortest path problems. While many researchers have observed that bidirectional A⋆ approaches perform poor...
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...
In the inventory routing problem (IRP) inventory management and route optimization are combined. The traveling salesman problem (TSP) is a special case of the IRP, hence the IRP is NP‐hard. We investigate how other aspects than routing influence the complexity of a variant of the IRP. We first study problem variants on a point and on the half‐line. The problems differ in the number of vehicles, the...
The primal adjacency‐based algorithm and the multidirectional dynamic programming algorithm are two exact methods that have recently been developed to efficiently solve the shortest path problem with resource constraints (SPPRCs). These methods are primal in the sense that they are able to produce sequences of feasible solutions using iterative exploration of the search space. Since the SPPRCs often...
We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Tree for short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate...
In this paper we implement a branch‐price and cut algorithm for a time dependent vehicle routing problem with time windows in which the goal is to minimize the total route duration. The travel time between two customers is given by a piecewise linear function on the departure time and, thus, it need not remain fixed along the planning horizon. We discuss different alternatives for the implementation...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.