Search results for "Combinatorial Optimization"
showing 10 items of 59 documents
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
2019
The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW hav…
New exact methods for the time-invariant berth allocation and quay crane assignment problem
2019
Abstract Efficient management of operations in seaport container terminals has become a critical issue, due to the increase in maritime traffic and the strong competition between ports. In this paper we focus on two seaside operational problems: the Berth Allocation Problem and the Quay Crane Assignment Problem, which are considered in an integrated way. For the continuous BACAP problem with time-invariant crane assignment we propose a new mixed integer linear model in which the vessels can be moored at any position on the quay, not requiring any quay discretization. The model is enhanced by adding several families of valid inequalities. The resulting model is able to solve instances with u…
The berth allocation problem in terminals with irregular layouts
2019
As international trade thrives, terminals attempt to obtain higher revenue while coping with an increased complexity with regard to terminal management operations. One of the most prevalent problems such terminals face is the Berth Allocation Problem (BAP), which concerns allocating vessels to a set of berths and time slots while simultaneously minimizing objectives such as total stay time or total assignment cost. Complex layouts of real terminals introduce spatial constraints which limit the mooring and departure of vessels. Although significant research has been conducted regarding the BAP, these real-world restrictions have not been taken into account in a general way. The present work …
Contributions to Close-Enough Arc Routing Problems
2021
A pesar de carecer de datos específicos, se estima que el sector del transporte representa aproximadamente el 64% del consumo mundial de combustible, el 27% del consumo total de energía y el 23% de las emisiones mundiales de dióxido de carbono (CO2) relacionadas con la energía. Además, se prevé que el impacto medioambiental del sector del transporte aumente de forma drástica en los próximos años debido al efecto de la globalización, que ha eliminado barreras haciendo posible la accesibilidad a todos los lugares, productos y servicios del mundo. Por ello, el transporte se sitúa como uno de los principales retos en materia de desarrollo, para impulsar la prosperidad y lograr así un entorno so…
Adaptive memory programing for the robust capacitated international sourcing problem
2008
The International Sourcing Problem consists of selecting a subset from an available set of potential suppliers internationally located. The selected suppliers must meet the demand for items from a set of plants, which are also located worldwide. Since the costs are affected by macroeconomic conditions in the countries where the supplier and the plant are located, the formulation considers the uncertainty associated with changes in these conditions. We formulate the robust capacitated international sourcing problem by means of a scenario-optimization approach. When dealing with uncertainty, one of the most common approaches in the literature is to formulate the problem via a set of possible …
Tabu search for min-max edge crossing in graphs
2020
Abstract Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min…
Packing a trunk - Now with a twist!
2005
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure. No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constrain…
Combinatorial Optimization for Artificial Intelligence Enabled Mobile Network Automation
2021
This chapter discusses combinatorial optimization techniques for enabling intelligent automation in mobile networks. A number of discrete optimization problems pertinent to mobile network automation can be solved effectively using artificial intelligence based combinatorial optimization approaches such as heuristics and metaheuristics. Relevant use-cases include both initial parameter assignment during network roll-out, and continuous optimization of configuration management parameters during network operation and maintenance. We discuss mobile network automation use-cases and motivation for using different heuristics and metaheuristics in designing network optimization algorithms. To this …
Some recent contributions to routing and location problems
2003
CORAL 2003, a Conference on Routing and Location, washeld in Puerto de la Cruz (Tenerife, Spain) from February24–26, 2003. A wonderful place, close to the black sand ofthe beach, and a nice temperature welcomed a group ofsenior and young researchers from Canada, England,France, Germany, and Spain. Social activities were alsoprovided and sponsored by the Cabildo Insular de Tenerife(the local government) and TITSA (the public bus transpor-tation company on the island). The conference corre-sponded to the third annual meeting of a research project,funded by the Spanish Ministry of Science and Technology,developing a Decision Support System for Vehicle Routingand Facility Location Problems (SAD…
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…