Search

This article presents a novel mathematical formulation to solve the problem of optimally sizing and managing battery energy storage for the solar photovoltaic system integration of a multi-apartmen...

In this chapter, we introduce multi-objective optimization, and recall some of the most relevant research articles that appeared in the literature related to this topic. The presented state of the art does not have the purpose of being exhaustive; it aims to drive the reader to the main problems and the approaches to solve them.

In this chapter, we introduce some aspects of freight distribution problems inherent to a maritime terminal, which represents the origin of the road and the rail shipments. This analysis also has the objective of introducing how simulation tools can be used to set capacity and service level.

In this chapter, we introduce freight distribution logistics, discussing some statistics about the current scenario and future trends in this area. Basically, it appears that, even though there has been a slight increase in the use of rail and water transportation modes, there is room to obtain a more efficient use of the road mode, mainly not to increase air pollution (fossil-fuel combustion represents about 80% of the factors that jeopardize air quality). In order to be able to reach an equilibrium among different transportation modes, the entire supply chain has to be studied to install the appropriate service capacity and to define effective operational procedures to optimize the system performance.

In this chapter, we introduce heterogeneous fleet delivery systems which are motivated by the availability of new technological devices (i.e., robots and drones), and by the large increase of goods deliveries to consumer locations. Both the growth of e-commerce logistics and the subsequent fragmentation of distribution flows in high density populated areas, call for more sustainable delivery systems able to reduce traffic and air pollution in city centers, where the adoption of medium-large trucks is not the best solution from many points of view. Beyond this general trend, there are a number of scenarios in which it is mandatory to adopt a heterogeneous fleet system. This is the case, for instance, when standard vehicles cannot access an area because of a large and not temporary interruption of the transportation infrastructure, damaged by an earthquake or a severe thunderstorm. For the above reasons, we will focus on (i) fleets with standard vehicles and drones working in tandem in post-disaster scenarios; (ii) truck and drone fleets for delivery of goods, and, (iii) fleets of bicycles or cargo bikes, whose use is growing very fast for deliveries in metropolitan areas.

In this chapter, we discuss green practices in supply chain management. First, we analyze green corridors, and then green network design problems. For both these problems, we present mathematical optimization models with two objectives: one related to transportation costs and the other to the protection of the environment. These two objectives are combined in both bi-objective and bi-level optimization programs. Solution techniques are given along with implementation codes and computational results.

In this chapter, we review some significant results in the arena of optimal route planning and risk evaluation of hazardous material transportation.

Bringing the cellular connectivity in rural zones is a big challenge, due to the large installation costs that are incurred when a legacy cellular network based on fixed Base Stations (BSs) is deployed. To tackle this aspect, we consider an alternative architecture composed of UAV-based BSs to provide cellular coverage, ground sites to connect the UAVs with the rest of the network, Solar Panels (SPs) and batteries to recharge the UAVs and to power the ground sites, and a ring of optical fiber links to connect the installed sites. We then target the minimization of the installation costs for the considered UAV-based cellular architecture, by taking into account the constraints of UAVs coverage, SPs energy consumption, levels of the batteries and the deployment of the optical ring. After providing the problem formulation, we derive an innovative methodology to ensure that a single ring of installed optical fibers is deployed. Moreover, we propose a new algorithm, called DIARIZE, to practically tackle the problem. Our results, obtained over a set of representative rural scenarios, show that DIARIZE performs very close to the optimal solution, and in general outperforms a reference design based on fixed BSs.

The aim of the sparse analytic hierarchy process (SAHP) problem is to rank a set of alternatives based on their utility/importance; this task is accomplished by asking human decision-makers to compare selected pairs of alternatives and to specify relative preference information, in the form of ratios of utilities. However, such an information is often affected by subjective biases or inconsistencies. Moreover, there is no general consent on the best approach to accomplish this task, and in the literature several techniques have been proposed. Finally, when more than one decision-maker is involved in the process, there is a need to provide adequate methodologies to aggregate the available information. In this view, the contribution of this paper to the SAHP body of knowledge is twofold. From one side, it develops a novel methodology to aggregate sparse data given by multiple sources of information. From another side, the paper undertakes an experimental validation of the most popular techniques to solve the SAHP problem, discussing the strength points and shortcomings of the different methodology with respect to a real case study.

In this paper we present a new model for train calendars textual generation, that is a method for automatically generating a text to customers in a concise and clear way with a service calendar represented by a boolean vector as its input. This problem arises in the transportation field, in particular in railway services. A new mathematical model which guarantees the optimality of solutions and good computational performances is described and tested on several real railway timetables, always obtaining optimal solutions. Moreover, it is extensively compared with existing models showing a significant reduction of computational times that makes it applicable in practical contexts.

Most of classical decision making processes aim at selecting the “best” alternative or at ranking alternatives based on the opinions of decision makers. Often, such a process occurs among people (experts or decision makers) who are expected to achieve some shared consensus in ranking the alternatives. However, this is not likely to happen (especially for a large and heterogeneous collection of people) and decision makers tend to reveal groups characteristics derived from their different opinions. A major problem is that inconsistency in opinions arises as each expert has a limited knowledge, errors and misinterpretation of data can occur and thus it is not clear how groups can be identified to be internally consistent and non-conflicting. In this paper, we investigate the conditions under which experts can be split into different sub-groups that share coherent and consistent opinions but are mutually in conflict in the ordering of the alternatives. We face this problem by presenting a non-linear integer programming model where each decision maker specifies incomplete preferences on pairs of alternatives and the objective is to obtain groups having the least possible degree of inconsistency. From a theoretical standpoint, we show that the proposed problem is non-convex and NP-Hard. Moreover, we validate the proposed approach with respect to a case study related to the 2018 Italian political elections. Specifically, we analyze the opinions of 33 decision makers and we show that the proposed technique is able to identify sub-groups characterized by large internal consistency, i.e., the members of each sub-groups express similar judgements upon the different options, while such options are evaluated very differently by the different sub-groups. Interestingly, while dividing the decision makers in three sub-groups, we obtain group rankings that reflect the structure of the Italian political parties or coalitions at the time, i.e., left-wing, right-wing and populists, even if such kind of information has not been directly provided by the decision makers nor used within the proposed case study.

This paper addresses a variant of the classical clique problem in which the edges of the graph are labeled. The problem consists of finding a clique as large as possible whose edge set contains at most b ∈ Z+ different labels. Moreover, in case of more feasible cliques of the same maximum size, we look for the one with the minimum number of labels. We study the time complexity of the problem, also in special cases, and we propose a mathematical programming approach for its solution by introducing two different formulations: the basic and the enforced. We experimentally evaluate the performance of the proposed approach on a set of benchmark instances (DIMACS) suitably adapted to the problem.

We optimally formulate the problem of maximizing the sustainability in a backbone network, with the goal of balancing network energy savings, device fixing costs, and users utility. Results show that the proposed solution is able to increase the operator revenue, while both a classical energy-saving approach and an always on solution tend to increase the operator costs.

In this paper, we present an aggregate mathematical model for air traffic flow management (ATFM), a problem of great concern both in Europe and in the United States. The model extends previous approaches by simultaneously taking into account three important issues: (i) the model explicitly incorporates uncertainty in the airport capacities; (ii) it also considers the trade-off between airport arrivals and departures, which is a crucial issue in any hub airport; and (iii) it takes into account the interactions between different hubs. The level of aggregation proposed for the mathematical model allows us to solve realistic size instances with a commercial solver on a PC. Moreover it allows us to compute solutions which are perfectly consistent with the Collaborative Decision-Making (CDM) procedure in ATFM, widely adopted in the USA and which is currently receiving a lot of attention in Europe. In fact, the proposed model suggests the number of flights that should be delayed, a decision that belongs to the ATFM Authority, rather than assigning delays to individual aircraft.

This paper describes a new method of generating text starting from a calendar, automatically and in a representation clear to customers. We focus in particular on railway applications. Railway undertakings are trying to improve their communication with commuters, employees and travelers, especially for the frequent occurrences of path modifications implying scattered calendars and not intelligible descriptions appearing in various outputs such as websites, mobile applications, timetable boards, train transport diagrams and books. We propose two alternative approaches for this challenging task. The first one combines a customized set covering problem formulation with a parallel vector generation algorithm. The second one integrates the vector generation problem in the set covering problem into a more complex mathematical model. Our aim is to verify that with a mathematical programming approach it is possible to improve the quality of outcomes in terms of intelligibility. We used a commercial mip solver (CPLEX 12.4) to solve the two models, while we designed a specific parallel algorithm for the vector generation problem in the first approach. The new solutions were tested on several real timetables and compared with the tools used so far.

In this paper we review the dry port concept and its outfalls in terms of optimal design and management of freight distribution. Some optimization challenges arising from the presence of dry ports in intermodal freight transport systems are presented and discussed. Then we consider the tactical planning problem of defining the optimal routes and schedules for the fleet of vehicles providing transportation services between the terminals of a dry-port-based intermodal system. An original service network design model based on a mixed integer programming mathematical formulation is proposed to solve the considered problem. An experimental framework built upon realistic instances inspired by regional cases is described and the computational results of the model are presented and discussed.

We consider the problem of extending device lifetime in backbone networks by exploiting sleep modes. In particular, when the device is put in sleep mode, its lifetime tends to increase. However, the transition between full power and sleep mode tends to decrease the lifetime. We model these two effects in an optimization problem, which considers the management of sleep modes in an operator network. Results, obtained on a realistic case study, show that the average lifetime of the devices in the network can be increased up to 43% compared to an always on solution.

Given a graph G with a label (color) assigned to each edge (not necessarily properly) we look for an hamiltonian cycle of G with the minimum number of difierent colors. The problem has several applications in telecommunication networks, electric networks, multimodal transportation networks, among others, where one aims to ensure connectivity or other properties by means of limited number of difierent connections. We analyze the complexity of the problem on special graph classes and propose, for the general case, heuristic resolution algorithms. Performances of the algorithms are experimentally evaluated on a set of instances and compared with the exact solution value provided by a solver.

Let \(T \, =\, \{T_1, T_2, \ldots, T_n\}\) be a set of n independent tasks and \(\mathcal{P}=\{P_1, P_2,\ldots, P_m\}\) a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs

We study various uniform k-partition problems which consist in partitioning m sets, each of cardinality k, into k sets of cardinality m such that each of these sets contains exactly one element from every original set. The problems differ according to the particular measure of “set uniformity” to be optimized. Most problems are polynomial and corresponding solution algorithms are provided. A few of them are proved to be NP-hard. Examples of applications to scheduling and routing problems are also discussed.

This paper has been motivated by the study of a real application, the transshipment container terminal of Gioia Tauro in Italy. The activities in a container terminal concern with the movement of containers from/to mother vessels and feeders and with the handling and storage of containers in the yard. For such type of applications both operational (e.g., scheduling) and tactical (e.g., planning) models, currently available in the literature, are not useful in terms of operations management and resources optimization. Indeed, the former models are too detailed for the complexity of the systems, while the latter are not able to capture the operational constraints in representing those activities which limit the nominal capacity. Herein, the container terminal, or more in general a service or production system, is represented as a network of complex substructures or platforms. The idea is to formalize the concept of platform capacity, which is used to represent the operational aspects of the container terminal in a mathematical model for the tactical planning. The problem, which consists in finding an allocation of resources in each platform in order to minimize the total delay on the overall network and on the time horizon, is modelled by a mathematical programming formulation for which we carry out a computational analysis using CPLEX-MIP solver. Moreover, we present a dynamic programming based heuristic to solve larger instances in short computational time. On all but one of the smaller instances, the heuristic solutions are also optimal. On the larger instances, the maximum gap, i.e. the percentage deviation, between the heuristic solutions and the best solutions computed by CPLEX-MIP within the time limit of 3600 s, has been 6.3%.

In this work we consider the problem of scheduling multiprocessor tasks on parallel processors available only in restricted intervals of time called time windows. The multiprocessor task model applies to modern production systems and parallel applications in which several processors can be utilized in parallel. Preemptable tasks are considered. Polynomial time algorithms are given in three cases: the case of maximum lateness criterion and a fixed number of processors, the case of schedule length criterion when tasks have various ready times and require either one or all processors, and in case of schedule length criterion when the sizes of the tasks are powers of 2.

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.

In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middle-high density graphs with quite a large difference between the maximum clique and the chromatic number.

Multiprocessor tasks are executed by more than one processor at the same moment of time. This work considers the problem of scheduling unit execution-time and preemptable multiprocessor tasks on m parallel identical processors to minimize mean flow time and mean weighted flow time. We analyze complexity status of the problem. When tasks have unit execution time and the number of processors is arbitrary the problem is shown to be computationally hard. Constructing an optimal preemptive schedule is also computationally hard in general. Polynomial algorithms are presented for scheduling unit execution time tasks when the number of processors is fixed, or the numbers of simultaneously required processors are powers of 2. The case of preemptable tasks requiring either 1 or m processors simultaneously is solvable in low-order polynomial time. Scope and purpose Efficient use of scarce resources is of vital importance both in computer and production systems. Scheduling theory attempts to provide guidelines and algorithms for efficient assignment of the resources to the activities. For a long time the classical scheduling theory assumed that a task can be executed only by one processor at the given moment of time. This assumption is too restrictive in the case of parallel computer systems and modern production systems where tasks (e.g. programs) can be processed on several processors in parallel. Therefore, a new scheduling model of multiprocessor tasks has been proposed recently. Multiprocessor tasks may require more than one processor simultaneously. In this work a deterministic multiprocessor task scheduling problem is analyzed. Most of the earlier publications on this subject assumed schedule length (makespan) optimality criterion. Here we consider different optimality criteria which are the mean flow time and the mean weighted flow time. These are important for the user of the computer system rather than for the owner of the computing facility because they are very closely related to the average waiting time observed by the user.

In this paper, we analyze the problem of deterministic scheduling of applications (programs) in a client-server environment. We assume that the client reads data from the server, processes it, and stores the results on the server. This paradigm can also model a wider class of parallel applications. The goal is to find the shortest schedule. It is shown that the general problem is computationally hard. However, any list scheduling algorithm delivers solutions not worse than twice the optimum when tasks are preallocated, and three times the optimum when tasks are not preallocated. A polynomially solvable case is also presented.

A set of items has to be assigned to a set of bins with different sizes. If necessary the size of each bin can be extended. The objective is to minimize the total size, i.e. the sum of the sizes of the bins. In this paper we study both the off-line case and the on-line variant of this problem under the assumption that each item is smaller than any bin. For the former case, when all times are known in advance, we analyze the worst-case performance of the longest processing time heuristic and prove a bound of 2(2 − √2). For the on-line case, where each incoming item has to be assigned immediately to a bin and the assignment cannot be changed later, we give a lower bound of 7 6 on the worst-case relative error of any on-line algorithm with respect to the off-line problem and we show that a list scheduling algorithm, which assigns the incoming item to the bin with biggest idle space, has a worst-case performance ratio equal to 5 4 . This bound is shown to be tight.

We consider the problem of scheduling jobs with release dates and sequence‐dependentprocessing times on a single machine to minimize the total completion time. We show thatthis problem is equivalent to the Cumulative Traveling Salesman Problem with additionaltime constraints. For this latter problem, we give a dynamic programming formulation fromwhich lower bounds are derived. Two heuristic algorithms are proposed. Performanceanalysis of both lower bounds and heuristics on randomly generated test problems are carriedout. Moreover, the application of the model and algorithms to the real problem of sequencinglanding aircraft in the terminal area of a congested airport is analyzed. Computational resultson realistic data sets show that heuristic solutions can be effective in practical contexts.

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.

A set of items has to be assigned to a set of bins with size one. If necessary, the size of the bins can be extended. The objective is to minimize the total size, i.e., the sum of the sizes of the bins. The Longest Processing Time heuristic is applied to this NP-hard problem. For this approximation algorithm we prove a worst-case bound of 13 12 which is shown to be tight when the number of bins is even.