Browsing by Author "Constantino, Miguel"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
- Dissimilar arc routing problemsPublication . Constantino, Miguel; Mourão, M. Cândida; Pinto, Leonor S.Money collection presents particular problems in terms of effective vehicle routing. Planning the collection or distribution of money for ATMs or parking meters gives rise to two problems: while the total collecting time should be minimized, tours on successive days should be different to prevent robberies. The combination of these two problems is named as the Dissimilar Routing Problem. When the safes to be collected are located along the streets, it corresponds to an arc routing problem, which we call DARP, and when the money is from ATMs, it corresponds to a vehicle routing problem, usually referred to as the peripatetic routing problem. The former problem arises in a Portuguese company in charge of street parking in Lisbon. The firm needs to define tours to collect safes from parking meters, minimizing the total collecting time. To avoid robberies these tours cannot be repeated or somehow anticipated. For this new problem, we present a mixed integer linear programming (MILP) model and develop a matheuristic. Preliminary experiments are provided with data that mimic the real confidential data. Results point to a good performance of the matheuristic, while the smaller instances can be solved to optimality with the MILP model and a commercial solver.
- A new mixed-integer programming model for harvest scheduling subject to maximum area restrictionsPublication . Constantino, Miguel; Martins, Isabel; Borges, J.G.Forest ecosystem management often requires spatially explicit planning because the spatial arrangement of harvests has become a critical economic and environmental concern. Recent research on exact methods has addressed both the design and the solution of forest management problems with constraints on the clearcut size, but where simultaneously harvesting two adjacent stands in the same period does not necessarily exceed the maximum opening size. Two main integer programming approaches have been proposed for this area restriction model. However, both encompass an exponential number of variables or constraints. In this work, we present a new integer programming model with a polynomial number of variables and constraints. Branch and bound is used to solve it. The model was tested with both real and hypothetical forests ranging from 45 to 1,363 polygons. Results show that the proposed model’s solutions were within or slightly above 1% of the optimal solution and were obtained in a short computation time.
- The mixed capacitated arc routing problem with non-overlapping routesPublication . Constantino, Miguel; Gouveia, Luís; Mourão, M. Cândida; Nunes, Ana CatarinaReal world applications for vehicle collection or delivery along streets usually lead to arc routing problems, with additional and complicating constraints. In this paper we focus on arc routing with an additional constraint to identify vehicle service routes with a limited number of shared nodes, i.e. vehicle service routes with a limited number of intersections. This constraint leads to solutions that are better shaped for real application purposes. We propose a new problem, the bounded overlapping MCARP (BCARP), which is defined as the mixed capacitated arc routing problem (MCARP) with an additional constraint imposing an upper bound on the number of nodes that are common to different routes. The best feasible upper bound is obtained from a modified MCARP in which the minimization criteria is given by the overlapping of the routes. We show how to compute this bound by solving a simpler problem. To obtain feasible solutions for the bigger instances of the BCARP heuristics are also proposed. Computational results taken from two well known instance sets show that, with only a small increase in total time traveled, the model BCARP produces solutions that are more attractive to implement in practice than those produced by the MCARP mode