排序方式: 共有36条查询结果,搜索用时 0 毫秒
1.
We present a new methodology for solving large-scale employee tour scheduling problems. An integer programming model is proposed
where tours are decomposed into shifts and start times. This formulation can model complex shift and start time rules for
both continuous and discontinuous scheduling problems. A branch-and-price approach is devised to solve this model efficiently.
The methodology was tested on the largest tour scheduling problems found in the open literature. In comparison with an alternative
implicit model, our approach showed superior computational performance. 相似文献
2.
Martin Fink Guy Desaulniers Markus Frey Ferdinand Kiermaier Rainer Kolisch François Soumis 《European Journal of Operational Research》2019,272(2):699-711
Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job’s time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models. 相似文献
3.
Wei Yang Itır Z. Karaesmen Pınar Keskinocak Sridhar Tayur 《Annals of Operations Research》2008,159(1):415-431
Fractional aircraft ownership programs, where individuals or corporations own a fraction of an aircraft, have revolutionized
the corporate aviation industry. Fractional management companies (FMC) manage all aspects of aircraft operations enabling
the owners to enjoy the benefits of private aviation without the associated responsibilities. We describe here the development
of a scheduling decision support tool for a leading FMC. We present mathematical models, exact and heuristic solution methods.
Our computational results using real and randomly generated data indicate that these models are quite effective in finding
optimal or near-optimal solutions. The first phase of the implementation of one of these models at the FMC led to a significant
improvement in effective utilization of the aircraft, reduction of costs due to reduced empty moves, and hence increased profits. 相似文献
4.
Gabriel Gutiérrez-Jarpa Guy Desaulniers Gilbert Laporte Vladimir Marianov 《European Journal of Operational Research》2010
In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers. 相似文献
5.
In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality. 相似文献
6.
We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time. 相似文献
7.
In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation.
In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes
place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning
problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm.
We show a trade-off between modeling power and computation times of both techniques. 相似文献
8.
We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver. 相似文献
9.
An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles 总被引:2,自引:0,他引:2
Nabila Azi Michel Gendreau Jean-Yves Potvin 《European Journal of Operational Research》2010,202(3):756-763
The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows. 相似文献
10.
Matias Sevel Rasmussen Tor Justesen Anders Dohn Jesper Larsen 《European Journal of Operational Research》2012
In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits. 相似文献