1,721,148 research outputs found
Dynamic ng-path relaxation for the delivery man problem
No full textThe ng-path relaxation was introduced by Baldacci, Mingozzi, and Roberti [Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283] for computing tight lower bounds to vehicle routing problems by solving a relaxation of the set-partitioning formulation, where routes are not necessarily elementary and can contain predefined subtours. The strength of the achieved lower bounds depends on the subtours that routes can perform. In this paper, we introduce a new general bounding procedure called dynamic ng-path relaxation that enhances the one of Baldacci, Mingozzi, and Roberti (2011) by iteratively redefining the subtours that routes can perform. We apply the bounding procedure on the well-known delivery man problem, which is a generalization of the traveling salesman problem where costs for traversing arcs depend on their positions along the tour. The proposed bounding procedure is based on column generation and computes a sequence of nondecreasing lower bounds to the problem. The final lower bound is used to solve the problem to optimality with a simple dynamic programming recursion. An extensive computational analysis on benchmark instances from the TSPLIB shows that the new bounding procedure yields better lower bounds than those provided by the method of Baldacci, Mingozzi, and Roberti (2011). Furthermore, the proposed exact method outperforms other exact methods recently presented in the literature and is able to close five open instances with up to 150 vertices
Editorial Special Issue: 'Algae and cyanobacteria: prospects and challenges for plant disease management'
No full textThe use of alternatives to synthetic products is recommended by the European Regulation No. 1107/2009 by placing plant protection products on the market and repealing Council Directives 79/117/EEC and 91/414/EEC. Indeed, the use of synthetic products has been restricted due to their impact on the environment and on human and animal health. In addition, a number of initiatives have recently been implemented at the European level within the ‘Green Deal’ that aims towards a green transition to contrast climate change and preserve the environment. One of the objectives of the ‘Green Deal’ is to reduce by 50% the use and risks of chemical pesticides in agriculture by 2030 that may lead to a more problematic management of plant pathogens. A new challenge for research is to reveal novel alternatives to chemical pesticides, such as algae and cyanobacteria since they are a source of many bioactive compounds.
The Special Issue “Algae and cyanobacteria: prospects and challenges for plant disease management” includes six research articles (Table 1) and three reviews providing innovative results on the potential of algae and cyanobacteria as useful tools for plant disease management. The research articles include studies both in vitro and in planta by using algae and cyanobacteria applied through different methods
Optimal Scheduling of Railway Track Possessions in Large-Scale Projects with Multiple Construction Works
No full textThis paper addresses the railway track possession scheduling problem (RTPSP), where a large-scale railway infrastructure project consisting of multiple construction works is to be planned. The RTPSP is to determine when to perform the construction works and in which track possessions while satisfying different operational constraints and minimizing the total construction cost. To find an optimal solution of the RTPSP, this paper proposes an approach that, first, transfers the nominal market prices into track-possession-based real prices, and then generates a schedule of the construction works by solving a mixed-integer linear-programming model for the given track blocking proposal. The proposed approach is tested on a real-life case study from the Danish railway infrastructure manager. The results show that, in 2 h of computing time, the approach is able to provide solutions that are within 0.37% of the optimal one for six different blocking proposals and two alternative construction providers, so it can be used as an effective support tool in the primary planning stage to suggest preferable track possessions within the existing railway services
The Electric Traveling Salesman Problem with Time Windows
No full textTo minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers
A Decomposition Method for Finding Optimal Container Stowage Plans
Full text linkIn transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time
New route relaxation and pricing strategies for the vehicle routing problem
No full textIn this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (cvrp) and the vehicle routing problem with time windows (vrptw) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351-385] for the cvrp. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's vrptw instances and significantly improves the running times of state-of-the-art algorithms for both vrptw and cvrp. Subject classifications: vehicle routing; time windows; dual ascent heuristic; column-and-cut generation. Area of review: Transportation. History: Received March 2010; revision received September 2010; accepted November 2010. © 2011 INFORMS
Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints
No full textThis paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated VRP (CVRP) and the VRP with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW. © 2011 Elsevier B.V. All rights reserved
An exact algorithm for the multitrip vehicle routing problem
No full textThe multitrip vehicle routing problem (MTVRP) is a variant of the capacitated vehicle routing problem where each vehicle can perform a subset of routes, called a vehicle schedule, subject to maximum driving time constraints. Despite its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle. We describe two setpartitioning- like formulations of the MTVRP. The first formulation requires the generation of all feasible routes, whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers. © 2013 INFORMS
- …
