Search results for "routing"
showing 10 items of 587 documents
Linear Programming Based Methods for Solving Arc Routing Problems
2000
From the pioneering works of Dantzig, Edmonds and others, polyhedral (i.e. linear programming based) methods have been successfully applied to the resolution of many combinatorial optimization problems. See Junger, Reinelt & Rinaldi (1995) for an excellent survey on this topic. Roughly speaking, the method consists of trying to formulate the problem as a Linear Program and using the existing powerful methods of Linear Programming to solve it.
A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
2010
In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instance…
Large multiple neighborhood search for the clustered vehicle-routing problem
2018
Abstract The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood…
A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem
2015
Abstract In the Synchronized Pickup and Delivery Problem (SPDP), user-specified transportation requests from origin to destination points have to be serviced by a fleet of homogeneous vehicles. The task is to find a set of minimum-cost routes satisfying pairing and precedence, capacities, and time windows. Additionally, temporal synchronization constraints couple the service times at the pickup and delivery locations of the customer requests in the following way: a request has to be delivered within prespecified minimum and maximum time lags (called ride times) after it has been picked up. The presence of these ride-time constraints severely complicates the subproblem of the natural column-…
Global sensitivity analysis in wastewater treatment modelling
2019
Global sensitivity analysis (GSA) is a valuable tool to support the use of mathematical models. GSA allows the identifcation of the effect of model and input factor uncertainty on the model response, also considering the effect due to the interactions among factors. During recent years, the wastewater modelling feld has embraced the use of GSA. Wastewater modellers have tried to transfer the knowledge and experience from other disciplines and other water modelling felds.
A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
2010
This work proposes an efficient method for solving the Distance-1 Edge Coloring problem (D1EC) for the assignment of orthogonal channels in wireless networks with changing topology. The coloring algorithm is performed by means of the simulated annealing method, a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme. Furthermore, a stateful implementation of the D1EC scheme is proposed, in which network coloring is executed upon topology changes. The stateful D1EC is also based on simulated annealing and reduces the algorithm’s convergence time by one order of magnitude in …
The Rural Postman Problem on mixed graphs with turn penalties
2002
In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total mi…
Optimal Local Routing Strategies for Community Structured Time Varying Communication Networks
2017
International audience; In time varying data communication networks (TVCN), traffic congestion, system utility maximization and network performance enhancement are the prominent issues. All these issues can be resolved either by optimizing the network structure or by selecting efficient routing approaches. In this paper, we focus on the design of a time varying network model and propose an algorithm to find efficient user route in this network. Centrality plays a very important role in finding congestion free routes. Indeed, the more a node is central, the more it can be congested by the flow coming from or going to its neighborhood. For that reason, classically, routes are chosen such that…
Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem
2012
This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cut…
Comparison of continuous and discontinuous Galerkin approaches for variable-viscosity Stokes flow
2015
We describe a Discontinuous Galerkin (DG) scheme for variable-viscosity Stokes flow which is a crucial aspect of many geophysical modelling applications and conduct numerical experiments with different elements comparing the DG approach to the standard Finite Element Method (FEM). We compare the divergence-conforming lowest-order Raviart-Thomas (RT0P0) and Brezzi-Douglas-Marini (BDM1P0) element in the DG scheme with the bilinear Q1P0 and biquadratic Q2P1 elements for velocity and their matching piecewise constant/linear elements for pressure in the standard continuous Galerkin (CG) scheme with respect to accuracy and memory usage in 2D benchmark setups. We find that for the chosen geodynami…