A Branch-and-Cut method for the Capacitated Location-Routing Problem

Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 customers, shows that 26 instances with five depots are solved to optimality, including all instances with up to 40 customers and three with 50 customers.     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (ρ_ST + 2) where ρ_ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to ρ_ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

一种新的求解约束P-中位问题的启发式算法

针对约束P-中位问题的特点,提出了一种新的启发式算法。该算法借鉴了蚁群算法的信息素学习机制,同时针对问题的结构设计了合理的对象分配方式。模拟计算表明,该算法具有更好的全局优化性能和计算效率。     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (_ST + 2) where _ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to _ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

The Capacitated p-facility Location Problem on the Real Line

The problem we address involves locating p new facilities to service a set of customers or fixed points on the real line such that a measure of total cost will be minimized. A basic form of this problem was investigated by Love (1976), who observed that the fixed points must be allocated in sequence to the new facilities in an optimal solution, and thus, the problem can be solved by a dynamic programming algorithm. Since then, other forms of the model have been investigated; however, in all cases it is assumed that the new facilities have unlimited capacity so that customer flows are always allocated to the nearest facility. The objective of this paper is to analyze the effect of capacity constraints on the optimal locations of the new facilities. A general fixed-cost function is also included to account for practical considerations such as zoning regulations, and to permit the facilities to be located anywhere on the line instead of only at the fixed vertices. A dynamic programming method is formulated to solve the problem when the variable cost components are increasing convex functions of travel distance. The problem is shown to be NP-hard under more general cost structures.     

New lower bound for the Capacitated Arc Routing Problem

We present a new lower bound, the Multiple Cuts Node Duplication Lower Bound, for the undirected Capacitated Arc Routing Problem. We prove that this new bound dominates the existing bounds for the problem. Computational results are also provided.     

A Global Repair Operator for Capacitated Arc Routing Problem

Capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable for small instances, heuristics and metaheuristic methods are widely adopted when solving CARP. This paper demonstrates one major disadvantage encountered by traditional search algorithms and proposes a novel operator named global repair operator (GRO) to address it. We further embed GRO in a recently proposed tabu search algorithm (TSA) and apply the resultant repair-based tabu search (RTS) algorithm to five well-known benchmark test sets. Empirical results suggest that RTS not only outperforms TSA in terms of quality of solutions but also converges to the solutions faster. Moreover, RTS is also competitive with a number of state-of-the-art approaches for CARP. The efficacy of GRO is thereby justified. More importantly, since GRO is not specifically designed for the referred TSA, it might be a potential tool for improving any existing method that adopts the same solution representation.     

Hybrid evolutionary algorithm for the Capacitated Centered Clustering Problem

The Capacitated Centered Clustering Problem (CCCP) consists of defining a set of p groups with minimum dissimilarity on a network with n points. Demand values are associated with each point and each group has a demand capacity. The problem is well known to be NP-hard and has many practical applications. In this paper, the hybrid method Clustering Search (CS) is implemented to solve the CCCP. This method identifies promising regions of the search space by generating solutions with a metaheuristic, such as Genetic Algorithm, and clustering them into clusters that are then explored further with local search heuristics. Computational results considering instances available in the literature are presented to demonstrate the efficacy of CS.     

Cost-based filtering algorithms for a Capacitated Lot Sizing Problem and the Constrained Arborescence Problem

Constraint Programming (CP) is a paradigm derived from artificial intelligence, operational research, and algorithmics that can be used to solve combinatorial problems. CP solves problems by interleaving search (assign a value to an unassigned variable) and propagation. Constraint propagation aims at removing/filtering inconsistent values from the domains of the variables in order to reduce the search space of the problem. In this thesis, we develop filtering algorithms for two complex combinatorial optimization problems: a Capacitated Lot Sizing Problem (CLSP) and the Constrained Arborescence Problem (CAP). Each of these problems has many variants and practical applications.The CLSP is the problem of finding an optimal production plan for single or multiple items while satisfying demands of clients and respecting resource restrictions. The CLSP finds important applications in production planning. In this thesis, we introduce a CLSP in CP. In many lot sizing and scheduling problems, in particular when the planning horizon is discrete and finite, there are stocking costs to be minimized. These costs depend on the time spent between the production of an order and its delivery. We focus on developing specialized filtering algorithms to handle the stocking cost part of a class of the CLSP. We propose the global optimization constraint StockingCost when the perperiod stocking cost is the same for all orders; and its generalized version, the IDStockingCost constraint (ID stands for Item Dependent).In this thesis, we also deal with a well-known problem in graph theory: the Minimum Weight Arborescence (MWA) problem. Consider a weighted directed graph in which we distinguish one vertex r as the root. An MWA rooted at r is a directed spanning tree rooted at r with minimum total weight. We focus on the CAP that requires one to find an arborescence that satisfies some side constraints (for example resource, degree, or diameter constraints) and that has minimum weight. The CAP has many real life applications in telecommunication networks, computer networks, transportation problems, scheduling problems, etc. After sensitivity analysis of the MWA, we introduce the CAP in CP. We propose a dedicated global optimization constraint to handle any known variant of the CAP in CP: the MinArborescence constraint. All the proposed filtering algorithms are analyzed theoretically and evaluated experimentally. The different experimental evaluations of these propagators against the state-of-the-art propagators show their respective efficiencies.     

Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.     

An optimization-based heuristic for the Multi-objective Undirected Capacitated Arc Routing Problem

The Multi-objective Undirected Capacitated Arc Routing Problem (MUCARP) is the optimization problem aimed at finding the best strategy for servicing a subset of clients localized along the links of a logistic network, by using a fleet of vehicles and optimizing more than one objective. In general, the first goal consists in minimizing the total transportation cost, and in this case the problem brings back to the well-known Undirected Capacitated Arc Routing Problem (UCARP). The motivation behind the study of the MUCARP lies in the study of real situations where companies working in the logistic distribution field deal with complex operational strategies, in which different actors (trucks, drivers, customers) have to be allocated within an unified framework by taking into account opposite needs and different employment contracts. All the previous considerations lead to the MUCARP as a benchmark optimization problem for modeling practical situations. In this paper, the MUCARP is heuristically tackled. In particular, three competitive objectives are minimized at the same time: the total transportation cost, the longest route cost (makespan) and the number of vehicles (i.e., the total number of routes). An approximation of the optimal Pareto front is determined through an optimization-based heuristic procedure, whose performances are tested and analyzed on classical benchmark instances.     

Capacitated Refueling Station Location Problem with Traffic Deviations Over Multiple Time Periods

In this paper, we consider the problem of locating refueling stations in a transportation network via mathematical programming. The proposed model is applicable for several alternative fuel types and is particularly suitable for hydrogen fuel. We assume that a central planner, a hydrogen manufacturer or a government agency, determines the locations of the refueling stations for a given intra-city transportation network while accounting for multi-period travel demand, nonlinear refueling station operational cost, and the deviations of travelers from their shortest routes to refuel. Incorporating demand patterns over multiple periods allows us to account for both short- and long-term variation in hydrogen refueling demand (the former due to time of day, and the latter future hydrogen fuel cell vehicle growth). It also helps us model the changes in user preferences (station and route choices) and traffic conditions over different periods. To account for refueling station operational cost in making investment decisions, we introduce a staircase marginal cost function. In addition, the model explicitly considers station and route choices of travelers as they may deviate from their original paths to refuel, incurring additional costs and affecting the number and locations of refueling stations. We formulate this problem as a multi-period, mixed-integer model with constant link travel time and staircase operational cost at refueling stations. We applied two well-known solution algorithms, branch-and-bound and Lagrangian relaxation, to solve the problem. Our analysis shows that although we are able to solve the refueling station location problem to optimality with branch-and-bound, the Lagrangian relaxation approach provides very good results with less computational time. Additionally, our numerical example of Mashhad, Iran demonstrates that locating refueling stations with considering multi-period traffic patterns (as opposed to single-period) results in minimum network-wide traffic congestion and lower user and agency costs over a planning horizon.     

能力约束及准备费用延用条件下批量问题的一种启发式算法

考虑能力约束及装备费用延用条件下的多部件批量问题。准备费用延用指如本期末与下期初生产同一部件,下期可节省其准备费用。提出了该问题的一种期间循进式启发算法。并进行了有关的仿真计算。     

A List Based Threshold Accepting Algorithm for the Capacitated Vehicle Routing Problem

The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the Capacitated Vehicle Routing Problem (CVRP), termed as the List Based Threshold Accepting (LBTA) algorithm. The main advantage of this algorithm over the majority of other meta-heuristics is that it produces quite satisfactory solutions in reasonable amount of time by tuning only one parameter of the algorithm. This property makes this algorithm a reliable and a practical tool for every decision support system designed for solving real life vehicle routing problems.     

Mobile Advertising in Capacitated Wireless Networks

The growing number of mobile subscribers has attracted firms to invent newer strategies to reach prospective customers in innovative but nonintrusive ways. While customer mobility creates an opportunity to reach them at desired times and locations, in practice, real-time ad deliveries are difficult due to the size of the ad-delivery decision problem. This research aims at analyzing and developing a decision policy for delivering ads on mobile devices such as cell phones. We look at the ad delivery problem from the perspective of an advertising firm, which delivers ads on behalf of its clients (merchants) to mobile customer using a wireless carrier's infrastructure. We formulate the mobile ad delivery problem as a Markov decision process (MDP) model. The ad delivery policy depends on the customer's desire and willingness to receive ads, their real-time locations, historical mobility patterns, available network capacity, and fee structure agreed upon for ad deliveries. We also develop a fast heuristic to solve larger size problems. We test our heuristic against an upper bound we developed and analyze performance using simulation.