We present a two-stage methodology called Positions and Covering (P&C) to solve the two-dimensional bin packing problem (2D-BPP). The objective of this classical combinatorial NP-hard problem is to ...pack a set of items (small rectangles) in the minimum number of bins (larger rectangles). The first stage is the key-point of the Positions and Covering, where for each item, it is generated in a pseudo-polynomial way a set of valid positions that indicate the possible ways of packing the item into the bin. In the second stage, a new set-covering formulation, strengthen with three sets of valid inequalities, is used to select the optimal non-overlapping configuration of items for each bin. Experimental results for the P&C method are presented and compared with some of the best algorithms in the literature for small and medium size instances. Furthermore, we are considering both cases of the 2D-BPP, with and without rotations of the items by 90°. To the best of our knowledge, this is one of the first exact approaches to obtain optimal solutions for the rotation case.
We use the Positions and Covering methodology to obtain exact solutions for the two-dimensional, non-guillotine restricted, strip packing problem. In this classical NP-hard problem, a given set of ...rectangular items has to be packed into a strip of fixed weight and infinite height. The objective consists in determining the minimum height of the strip. The Positions and Covering methodology is based on a two-stage procedure. First, it is generated, in a pseudo-polynomial way, a set of valid positions in which an item can be packed into the strip. Then, by using a set-covering formulation, the best configuration of items into the strip is selected. Based on the literature benchmark, experimental results validate the quality of the solutions and method's effectiveness for small and medium-size instances. To the best of our knowledge, this is the first approach that generates optimal solutions for some literature instances for which the optimal solution was unknown before this study.
Display omitted
•We develop a complete integration of timetabling and vehicle scheduling problems.•Our methodology formulates a bi-objective problem and use the ∊-constraint algorithm.•Obtained ...solutions can be used to measure the compromise between quality and costs.•We answer questions such as how many passengers are benefited by using one more bus?
In transit systems there is a critical trade-off between the level of service and operating costs. At the planning level, for a given network design, this trade-off is captured by the timetabling (TT) and vehicle scheduling (VS) problems. In the TT problem we try to maximize the number of passengers benefited by well timed transfers, while in the VS problem we seek to minimize the operating costs, which are related to the fleet size. This paper presents two integer linear programming models for the TT and VS problems, and combines them in a bi-objective integrated model. We propose and implement an ∊-constraint method to jointly solve this TT and VS bi-objective problem. This allows to analyze the trade-off between these two criteria in terms of Pareto fronts. Numerical experiments show that our proposed approach can solve scenarios with up to 50 bus lines.
•Tackle a new problem focusing on finished products in mold-injection manufacturing.•Develop a mathematical programming based heuristic for lot-sizing and scheduling.•Efficiently deal with lot-size ...of pieces and multiple mold-machine assignments.•Propose new data set for the problem to show advantages of the methodology.•Found high quality solutions using real data from companies to maximize profit.
This paper studies a lot-sizing and scheduling problem to maximize the profit of assembled products over several periods. The setting involves a plastic injection production environment where pieces are produced using auxiliary equipment (molds) to form finished products. Each piece may be processed in a set of molds with different production rates on various machines. The production rate varies according to the piece, mold and machine assignments. The novelty lies on the problem definition, where the focus is on finished products. We developed a two-stage iterative heuristic based on mathematical programming. First the lot-size of the products is determined together with the mold-machine assignments. The second stage determines if there is a feasible schedule of the molds with no overlapping. If unsuccessful, it goes back to the first stage and restricts the number of machines that a mold can visit, until a feasible solution is found. This decomposition approach allows us to deal with a more complex environment that incorporates idle times and assembly line considerations. We show the advantages of this methodology on randomly generated instances and on data from real companies. Experimental results show that our heuristic converges to a feasible solution with few iterations, obtaining solutions that the companies find competitive both in terms of quality and running times.
Synchronization of bus timetabling IBARRA-ROJAS, Omar J; RIOS-SOLIS, Yasmin A
Transportation research. Part B: methodological,
06/2012, Letnik:
46, Številka:
5
Journal Article
Recenzirano
Timetable generation is a subproblem of bus network strategic planning, in which the departure time of each trip is determined. We study the bus network of Monterrey, Mexico, which is similar to ...those of other cities in Latin America. It is a large bus network where passenger transfers must be favored, almost evenly spaced departures are sought, and bus bunching of different lines must be avoided. We formulate the timetabling problem of this network with the objective of maximizing the number of synchronizations to facilitate passenger transfers and avoid bus bunching along the network. We define these synchronizations as the arrivals of two trips with a separation time within a time window to make a flexible formulation. This flexibility is a critical aspect for the bus network, since travel times vary because of reasons such as driver speed, traffic congestion, and accidents. By proving that our problem is NP-hard we answer a 10-year-old open question about the NP-hardness of similar problems present in literature. Next, we analyze the structural properties of the feasible solution space of our model. This analysis leads to a preprocessing stage that eliminates numerous decision variables and constraints. Moreover, this preprocessing defines feasible synchronization and arrival time windows that are used in a new metaheuristic algorithm. Empirical experimentation shows that our proposed algorithm obtains high-quality solutions for real-size instances in less than one minute.
•We study the integrated bus vehicle and reliable driver scheduling problem.•Driver’s reliability is the key concept that improves the operational assignments.•We reduce the number of no-covered to ...improve the user’s satisfaction.•A constraint programming model is compared with a variable neighborhood search.•Enormous gains obtained in covered trips when the drivers’ reliability is considered.
We propose the bus vehicle and reliable driver scheduling problem that is an integrated approach for the vehicle and the crew scheduling problems considering driver’s reliability information to reduce the number of no-covered trips along the day and thus improve the user’s satisfaction. An exact constraint programming model is proposed and compared with a variable neighborhood search that incorporates the driver’s reliability and the trip’s importance. The obtained trip-vehicle-driver assignments are evaluated on many scenarios with a Monte Carlo method to simulate the driver’s absenteeism. Experimental results on randomly generated instances based on a real case study show our methodologies’ efficiency and the enormous gains in covered trips when the drivers’ reliability is considered.
Multiperiod Bus Timetabling Ibarra-Rojas, Omar J.; López-Irarragorri, Fernando; Rios-Solis, Yasmin A.
Transportation science,
08/2016, Letnik:
50, Številka:
3
Journal Article
Recenzirano
Odprti dostop
The timetabling subproblem of bus transit network planning determines the departure times for all trips of the lines along the entire day. Most of the public transport networks consider planning ...periods identical for all lines. In this study we drop this strong assumption by introducing specific periods for each line, which is more realistic. Thus, we propose the multiperiod synchronization bus timetabling (MSBT) problem, which specifies the departure times of the trips of all lines where each line has its own planning periods along the day, with the objective of optimizing synchronization events: maximize passenger transfers and minimize bus bunching along the network.
We propose an integer linear programming formulation for the MSBT problem and analyze the structural properties of this formulation by a constraint propagation methodology. These properties are the basis for different operators that lead to the design of efficient metaheuristics for solving the problem. We empirically obtain high-quality feasible solutions for real size instances and show that by considering a multiperiod approach, synchronization events of trips belonging to different planning periods are not ignored, as it is the case when several single period timetables are merged.
•Drivers duty and Vehicles usage directly affects the operation costs of bus transportation agencies.•We introduce a new integration of the Vehicle Scheduling Problem (VSP) and the Crew Scheduling ...Problem (CSP).•The integration of the VSP and the CSP provides a more flexible transportation system and aims to reduce the overall operation cost.•We do not consider a fixed duty structure, and we include labor regulation constraints for the daily duty of the drivers.•The proposed Variable Neighborhood Search Algorithm can provide high quality solution in a short processing time for the real size instances.
This article deals with the Flexible Vehicle and Crew Scheduling Problem faced by urban bus transport agencies that have to assign their resources (vehicles and drivers) to cover timetables generated at the tactical level. We aim for high quality and fast to compute solutions for this problem, considering vehicle characteristics, driver qualifications requirements for each line, and labor regulations, that is, drivers have a limited duty length, mandatory rests, a restricted consecutive driving time, and a limited extra working hours. Moreover, the starting time of the drivers shift is not fixed a priori and the breaks can be allocated anywhere in the schedule as long as labor regulations are satisfied. Thus, flexibility is required to compute drivers duty but it is also needed in scenarios where the available number of drivers and vehicles changes almost everyday. We propose a mixed-integer linear programming model and a variable neighborhood search for this problem and show the efficiency of our approaches with a large set of instances.
We study the Maximal Covering Location Problem with Accessibility Indicators and Mobile Units that maximizes the facilities coverage, the accessibility of the zones to the open facilities, and the ...spatial disaggregation. The main characteristic of our problem is that mobile units can be deployed from open facilities to extend the coverage, accessibility, and opportunities for the inhabitants of the different demand zones. We formulate the Maximal Covering Location Problem with Accessibility Indicators and Mobile Units as a mixed-integer linear programming model. To solve larger instances, we propose a matheuristic (combination of exact and heuristic methods) composed of an Estimation of Distribution Algorithm and a parameterized Maximal Covering Location Problem with Accessibility Indicators and Mobile Units integer model. To test our methodology, we consider the Maximal Covering Location Problem with Accessibility Indicators and Mobile Units model to cover the low-income zones with Severe Acute Respiratory Syndrome Coronavirus 2 patients. Using official databases, we made a set of instances where we considered the poverty index, number of population, locations of hospitals, and Severe Acute Respiratory Syndrome Coronavirus 2 patients. The experimental results show the efficiency of our methodologies. Compared to the case without mobile units, we drastically improve the coverage and accessibility for the inhabitants of the demand zones.
•A new version of maximal covering location problem is introduced.•Mobile units related to the facilities optimize the accessibility indicators.•The instances set proposed is based on the COVID-19 situation in Mexico.•A mixed-integer linear programming model solves small and medium size instances.•A matheuristic is proposed to solve large instances.
•We tackle the bi-objective single p-batching machine problem of minimizing maximum lateness and number of jobs with a restricted batch size.•We applied an epsilon-constraint method and develop new ...mathematical models that are enhanced with a family of valid inequalities and constraints that avoid symmetric solutions.•We find Pareto-optimal solutions in reasonable times for up to 50 jobs.•We develop a BRKGA for larger instances of up to 100 jobs with good results with smaller computational times than the exact methods.
In this work, we consider a batching machine that can process several jobs at the same time. Batches have a restricted batch size, and the processing time of a batch is equal to the largest processing time among all jobs within the batch. We solve the bi-objective problem of minimizing the maximum lateness and number of batches. This function is relevant as we are interested in meeting due dates and minimizing the cost of handling each batch. Our aim is to find the Pareto-optimal solutions by using an epsilon-constraint method on a new mathematical model that is enhanced with a family of valid inequalities and constraints that avoid symmetric solutions. Additionally, we present a biased random-key genetic algorithm to approximate the optimal Pareto points of larger instances in reasonable time. Experimental results show the efficiency of our methodologies.
PDF
