Heuristics for routes generation in pickup and delivery problem

In shipping services, the goal is to propose cyclical routes which ensure transport of required goods among the main centers of the regions. It is classified as a pickup and delivery problem with split demand and reloading. The objective is to minimize total shipping costs, or the total length of all cyclical routes. The optimum solution gives a number of vehicles going on arcs of the communication network and the amount of goods being transported on the arcs. Consequently, cyclical routes and depots are proposed for all vehicles. First, the multi-graph, in which each directed arc corresponds to exactly one vehicle, is generated. The multi-graph satisfies the condition that the number of arcs entering each node equals the number of arcs exiting the node. The heuristic method of loading goods onto a vehicle in the pickup node and to transport it to the delivery node without reloading onto another vehicle is proposed. The method is verified in the case study carried out on the DHL company.     

小区间内一个素数和三个素数的平方和问题

研究了把一个满足必要条件的自然数在小区间内分解成一个素数和三个素数平方和的问题,利用刘建亚和展涛处理扩大了的主区间的新方法,成功的缩短了小区间的长度.     

Bounds on penalties for dummy arcs in transportation networks

In several resource allocation problems, one encounters transportation networks which may or may not be feasible, and which may also be accompanied by side constraints. In such contexts, one typically constructs some dummy transportation arcs with associated penalties, which either serve the role of facilitating a convenient starting solution, or seeking a solution to an infeasible problem which minimizes the total flow on the dummy arcs. In either case, particularly when the original transportation problem is infeasible, one would like to know a preferably small lower bound on the dummy arc penalties which could be validly employed. This paper derives such a bound. Extensions to more general networks are also addressed.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

A Partitioned ∈-Relaxation Algorithm for Separable Convex Network Flow Problems

A relaxation method for separable convex network flow problems is developed that is well-suited for problems with large variations in the magnitude of the nonlinear cost terms. The arcs are partitioned into two sets, one of which contains only arcs corresponding to strictly convex costs. The algorithm adjusts flows on the other arcs whenever possible, and terminates with primal-dual pairs that satisfy complementary slackness on the strictly convex arc set and -complementary slackness on the remaining arcs. An asynchronous parallel variant of the method is also developed. Computational results demonstrate that the method is significantly more efficient on ill-conditioned networks than existing methods, solving problems with several thousand nonlinear arcs in one second or less.     

Packing Transitive Triples in a Tournament

We prove that a tournament with n vertices has more than arc-disjoint transitive triples, and more than arc-disjoint transitive quadruples, improving earlier bounds. In particular, 82 percent of the arcs of a tournament can be packed with transitive triples and 45 percent of the arcs of a tournament can be packed with transitive quadruples. Our proof is obtained by examining the fractional version of the problem and utilizing a connection between the integral and fractional versions. Received October 12, 2005     

A hybrid simulated annealing and column generation approach for capacitated multicommodity network design

This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.     

A dual ascent approach to the fixed-charge capacitated network design problem

In this paper we consider the problem of constructing a network over which a number of commodities are to be transported. Fixed costs are associated to the construction of network arcs and variable costs are associated to routing of commodities. In addition, one capacity constraint is related to each arc. The problem is to determine a network design that minimizes the total cost; i.e., it balances the construction and operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated network design problem is proposed. The method is shown to generate tighter lower bounds than the linear programming relaxation of the problem.     

Approximation of the classical isoperimetric problem

Hestenes' method of multipliers is used to approximate the classical isoperimetric problem. A suitable sufficiency theorem is first applied to obtain minimizing arcs for a family of unconstrained problems. Given an initial estimate of the Lagrange multipliers, a convergent sequence of arcs is generated. They are minimizing with respect to members of the above family, and their limit is the solution to the original isoperimetric problem.The preparation of this paper was sponsored in part by the U.S. Army Research Office under Grant DA-31-124-ARO(D)-355.     

The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

New results for the Directed Profitable Rural Postman Problem

We study a generalization of the Directed Rural Postman Problem where not all arcs requiring a service have to be visited provided that a penalty cost is paid if a service arc is not crossed. The problem, known as Directed Profitable Rural Postman Problem, looks for a tour visiting the selected set of service arcs while minimizing both traveling and penalty costs. We add different valid inequalities to a known mathematical formulation of the problem and develop a branch-and-cut algorithm that introduces connectivity constraints both in a “lazy” and in a standard way. We also propose a matheuristic followed by an improvement heuristic (final refinement). The matheuristic exploits information provided by a problem relaxation to select promising service arcs used to solve optimally Directed Rural Postman problems. The ex-post refinement tries to improve the solution provided by the matheuristic using a branch-and-cut algorithm. The method gets a quick convergence through the introduction of connectivity cuts that are not guaranteed to be valid inequalities, and thus may exclude integer feasible solutions.     

On the numerical analysis of the Von Karman equations: Mixed finite element approximation and continuation techniques

Summary The purpose of this paper is to study the approximation of the Von Karman equations by the mixed finite element scheme of Miyoshi and to follow the solutions arcs at a neighbourhood of the first eigenvalue of the linearized problem. This last problem is solved by a continuation method.     

A general approach for optimizing regular criteria in the job-shop scheduling problem

Even though a very large number of solution methods has been developed for the job-shop scheduling problem, a majority has been designed for the makespan criterion. In this paper, we propose a general approach for optimizing any regular criterion in the job-shop scheduling problem. The approach is a local search method that uses a disjunctive graph model and neighborhoods generated by swapping critical arcs. The connectivity property of the neighborhood structure is proved and a novel efficient method for evaluating moves is presented. Besides its generality, another prominent advantage of the proposed approach is its simple implementation that only requires to tune the range of one parameter. Extensive computational experiments carried out on various criteria (makespan, total weighted flow time, total weighted tardiness, weighted sum of tardy jobs, maximum tardiness) show the efficiency of the proposed approach. Best results were obtained for some problem instances taken from the literature.     

Solving a k-Node Minimum Label Spanning Arborescence Problem to Compress Fingerprint Templates

We present a novel approach for compressing relatively small unordered data sets by means of combinatorial optimization. The application background comes from the field of biometrics, where the embedding of fingerprint template data into images by means of watermarking techniques requires extraordinary compression techniques. The approach is based on the construction of a directed tree, covering a sufficient subset of the data points. The arcs are stored via referencing a dictionary, which contains “typical” arcs w.r.t. the particular tree solution. By solving a tree-based combinatorial optimization problem we are able to find a compact representation of the input data. As optimization method we use on the one hand an exact branch-and-cut approach, and on the other hand heuristics including a greedy randomized adaptive search procedure (GRASP) and a memetic algorithm. Experimental results show that our method is able to achieve higher compression rates for fingerprint (minutiae) data than several standard compression algorithms.     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408-427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

Singular Arcs in the Generalized Goddard’s Problem

We investigate variants of Goddard’s problems for nonvertical trajectories. The control is the thrust force, and the objective is to maximize a certain final cost, typically, the final mass. In this article, performing an analysis based on the Pontryagin maximum principle, we prove that optimal trajectories may involve singular arcs (along which the norm of the thrust is neither zero nor maximal), that are computed and characterized. Numerical simulations are carried out, both with direct and indirect methods, demonstrating the relevance of taking into account singular arcs in the control strategy. The indirect method that we use is based on our previous theoretical analysis and consists in combining a shooting method with an homotopic method. The homotopic approach leads to a quadratic regularization of the problem and is a way to tackle the problem of nonsmoothness of the optimal control. Support from the French Space Agency CNES (Centre National d’Etudes Spatial) is gratefully acknowledged.     

Maximum path digraphs

In this paper we solve the following problem: Given an integer m, construct a digraph with exactly one source s, exactly one sink t and exactly m arcs such that the number of paths from s to t is maximized.     

The Mixed Problem for the Laplace Equation in an Exterior Domain with an Arbitrary Partition of the Boundary

In this paper we propose a method for solving the mixed boundary-value problem for the Laplace equation in a connected exterior domain with an arbitrary partition of the boundary. All simple closed curves making up the boundary are divided into three sets. On the elements of the first set the Dirichlet condition is given, on the elements of the second set the third boundary condition is prescribed, and the third set, in turn, is divided into two subsets of simple closed arcs, with the Dirichlet condition prescribed on the elements of one of these subsets and the third boundary condition on the elements of the other subset. The problem is reduced to a uniquely solvable Fredholm equation of the second kind in a Banach space. The third boundary-value problem and the mixed Dirichlet--Neumann problem are particular cases of the problem under study.