196,402 research outputs found
An Exact Algorithm for the Simplified Multi Depot Crew Scheduling Problem
No full textThe Multiple Depot Crew Scheduling Problem (MD-CSP) appears in public transit systems (e.g., airline, bus and railway industry) and consists of determining the optimal duties for a set of crews (or vehicles) split among several depots in order to cover a set of timetabled trips satisfying a number of constraints. We consider the case in which every crew must return to the starting depot and limits are imposed on both the elapsed time and the working time of any duty. The MD-CSP is an extension of both the Multiple Depot Vehicle Scheduling Problem (MD-VSP) and the single depot Crew Scheduling Problem (CSP). The MD-CSP is formulated as a set partitioning problem with side constraints (SP), where each column corresponds to a feasible duty. In this paper we extend to the MD-CSP the exact method used by Bianco, Mingozzi and Ricciardelli (1994) for MD-VSP and that used by Mingozzi et al. (1999) for the CSP. We also introduce a new bounding procedure based on Lagrangian relaxation and column generation which can deal with the MD-CSP constraints. The computational results for both random and real-world test problems from the literature show that the new exact procedure outperforms, on the test problems used, other exact methods proposed in the literature for the MD-VSP and the CSP
The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds
No full textThis paper is the second of a two part series and describes new lower and upper bounds for a more general version of the Two-Dimensional Finite Bin Packing Problem (2BP) than the one considered in Part I (see Boschetti and Mingozzi 2002). With each item is associated an input parameter specifying if it has a fixed orientation or it can be rotated by 90°. This problem contains as special cases the oriented and non-oriented 2BP. The new lower bound is based on the one described in Part I for the oriented 2BP. The computational results on the test problems derived from the literature show the effectiveness of the new proposed lower and upper bounds. © 2003 Springer-Verlag Berlin/Heidelberg
The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case
No full textThe Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by 90°. Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds. © 2003 Springer-Verlag Berlin/Heidelberg
In vitro cultivation of donor quince shoots affects subsequent morphogenesis in leaf explants
No full textThe effect of in vitro cultivation of donor shoots on subsequent morphogenesis in leaf explants of quince (Cydonia oblonga Mill.) clone BA29 was investigated. Proliferating donor shoots were cultured in ventilated or closed vessels under different photosynthetic photon flux densities (PPFD; 200 and 100 μmol m-2 s-1) with 0, 15, 30 g dm-3 sucrose. Shoots grown in ventilated vessels, especially with sucrose at 15 or 30 g dm-3, were better developed with fully expanded leaves compared to those in standard closed vessels. Leaves collected from pre-treated donor shoots were used to assess regeneration capacity. Somatic embryo production was highest in leaves harvested from shoots cultured in closed vessels with 30 g dm-3 sucrose and in ventilated vessels with 15 and 30 g dm -3 sucrose and under high PPFD which was, in comparison with the control treatment (closed vessel, 30 g dm-3 sucrose and low PPFD), about 2 to 2.5 times higher. A similar response was observed for root regeneration
The Multi-depot Periodic Vehicle Routing Problem Abstraction, Reformulation and Approximation
No full textThe Multi-Depot Periodic Vehicle Routing Problem (MDPVRP) is the problem of designing, for an homogeneous fleet of vehicles of capacity Q, a set of routes for each day of a given p-day period. The routes of day k must be executed by m k vehicles based at the depot assigned to day k. Each vehicle performs only one route per day and each vehicle route must start and finish at the same depot. Each customer i may require to be visited on f i (say) di.erent days during the period and these visits may only occur in one of a given number of allowable daycombinations. For example, a customer may require to be visited twice during a 5-day period imposing that these visits should take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The MDPVRP consists of simultaneously assigning a day-combination to each customer and designing the vehicle routes for each day of the planning period so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available at the depot assigned to that day and the total cost of the routes is minimized
Stress osmotico indotto da saccarosio e PEG : incremento dei fenoli totali, attività antiossidante e prolina in Achillea in vitro
No full textE’ stato indagato l’effetto di saccarosio e PEG, utilizzati al fine indurre stress osmotico, sul livello di fenoli totali, attività antiossidante e accumulo di prolina in foglie e radici di piante di Achillea collina allevate in vitro. L’incremento della concentrazione di saccarosio dal 3 al 12% ha determinato una significativa riduzione dello sviluppo di foglie e radici. Il livello di fenoli totali mostrava un incremento progressivo all’aumentare della concentrazione di saccarosio ed era 3 volte più elevato nelle foglie di piante cresciute in presenza di saccarosio al 12% rispetto al controllo (3% saccarosio). Analogo andamento mostrava l’attività antiossidante degli estratti metanolici di achillea, sebbene l’effetto della concentrazione più elevata di saccarosio fosse meno pronunciato. Il livello della prolina mostrava un notevole incremento sia nelle foglie sia nelle radici delle piante cresciute ad alti livelli di saccarosio. Al fine di approfondire le indagini sull’effetto dello stress osmotico su achillea allevata in vitro, sono stati attuati esperimenti utilizzando PEG6000 come osmolita. Piante allevate con saccarosio al 3% più il 3 o 6% di PEG mostravano una riduzione significativa della crescita e un incremento significativo dei fenoli totali, dell’attività antiossidante e del livello di prolina rispetto al controllo
Partitioning a matrix to minimize the maximum cost
No full textAbstractA matrix A = [aij] of nonnegative integers must be partitioned into p blocks (submatrices) corresponding to a set of vertical cuts parallel to the columns and a set of horizontal cuts parallel to the rows. With each block is associated a cost equal to the sum of its elements. We consider the problem of finding a matrix partitioning that minimizes the cost of the block of maximum cost.In this paper a mathematical formulation of the problem is given and used to derive both exact and heuristic algorithms.Lower bounds and dominance criteria are exploited in a tree search algorithm for finding the optimal solution of the problem. Computational results of the proposed algorithm are given on a number of randomly generated test problems
Partitioning a matrix with non-guillotine cuts to minimize the maximum cost
No full textAbstractWe consider the problem of partitioning a matrix of m rows and n columns of non-negative integers into M smaller submatrices. With each submatrix is associated a cost equal to the sum of its elements. The objective is to minimize the cost of the submatrix of maximum cost. We present a (0–1)-integer programming formulation of the problem and three different lower bounds. A heuristic procedure for finding a valid upper bound to the optimal solution cost is also described. Problem reduction tests derived from both the original problem and the lower bounds are given. Lower bounds and reduction tests are used in a tree search algorithm in order to find the optimal solution to the problem. Computational results on a number of randomly generated test problems are presented
- …
