Search

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.

RÉSUMÉDans cet article, nous revenons sur la critique tout à fait originale de l'utilitarisme que Philippa Foot propose dans son œuvre de philosophie morale. Nous montrerons que la confrontation avec cette théorie éthique normative fut l'une des causes qui conduisit la philosophe britannique à reprendre à nouveaux frais la notion de rationalité pratique dans la dernière partie de son œuvre, notamment lors de la discussion qu'elle engage avec l'utilitarisme sur le fondement de l'obligation des promesses dans son livre de 2001, Le Bien naturel.

The multi-activity shift scheduling problem involves assigning a sequence of activities to a set of employees. In this paper, we consider the variant where the employees have different qualifications and each activity must be performed in a specified time window; i.e., we specify the earliest start period and the latest finish period. We propose a matheuristic in which Lagrangian relaxation is used to identify a subset of promising shifts, and a restricted set covering problem is solved to find a feasible solution. Each shift is represented by a context-free grammar. Computational tests are carried out on two sets of instances from the literature. For the first set, the matheuristic finds a solution with an optimality gap less than 0.01% for 70% of the instances and improves the best-known solution for 16% of them; for the second set, the matheuristic reaches the best-known solutions for 55% of the instances and finds better solutions for 37.5% of them.

International audience; The multiplication of computing cores in modern processor units permits revisiting the design of classical algorithms to improve computational performance in complex application domains. Artificial Intelligence planning is one of those applications where large search spaces require intelligent and more exhaustive search control. In this paper, parallel planning algorithms, derived from best-first search, are proposed for shared memory architectures. The parallel algorithms, based on the asynchronous work pool paradigm, maintain good thread occupancy in multi-core CPUs. All algorithms use one ordered global list of states stored in shared memory from where they select nodes for expansion. A parallel best-first search algorithm that develops new states with depth equal to one is proposed first. Then, we propose an extension of this parallel algorithm that features a diversification strategy in order to escape local minima. We study and analyse a set of computational experiments for problems that come from the International Planning Competition and real-world industry applications. The empirical evaluation shows that the parallel algorithms solve most of the domains efficiently without incurring higher solutions costs. In those problems with partial results, we highlight the potential shortcomings of the proposed approaches for promising future directions.

The QSNET consortium is building a UK network of next-generation atomic and molecular clocks that will achieve unprecedented sensitivity in testing variations of the fine structure constant, $\alpha$, and the electron-to-proton mass ratio, $\mu$. This in turn will provide more stringent constraints on a wide range of fundamental and phenomenological theories beyond the Standard Model and on dark matter models.

The IEEE Workshop on Parallel / Distributed Combinatorics and Optimization aims at providing a forum for scientific researchers and engineers on recent advances in the field of parallel or distributed computing for difficult combinatorial optimization problems, like 0–1 multidimensional knapsack problems, cutting stock problems, scheduling problems, large scale linear programming problems, nonlinear optimization problems and global optimization problems. Emphasis is placed on new techniques for the solution of these difficult problems like cooperative methods for integer programming problems. Techniques based on metaheuristics and nature-inspired paradigms are considered. Aspects related to Combinatorial Scientific Computing (CSC) are considered. In particular, we solicit submissions of original manuscripts on sparse matrix computations, graph algorithm and original parallel or distributed algorithms. The use of new approaches in parallel and distributed computing like GPU, MIC, FPGA, volunteer computing are considered. Application to cloud computing, planning, logistics, manufacturing, finance, telecommunications and computational biology are considered.

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.

In this work, we introduce a Flexible Job-shop Scheduling Problem with Resource Recovery Constraints (FRRC). In the FRRC, besides the constraints of the classical Flexible Job-shop Scheduling Probl...

This paper introduces a variant of the well-known Multi-Depot Periodic Vehicle Routing Problem, which is inspired by a real situation of a distribution company. The problem consists in determining the number of extra vehicles to rent, the assignment of vehicles to plants, and the routes between plants and distribution centers, while the transportation cost is minimized. We propose a mixed integer linear formulation and a Reactive Greedy Randomized Adaptive Search Procedure to solve the problem. Extensive computational results show that the proposed procedure provides high-quality solutions with an average gap lower than 2.5% from the computed lower bound.

In this work, we introduce a generalized flexible job-shop scheduling problem in which, besides the classical constraints of the flexible job shop scheduling problem other hard constraints such as machine capacity, time lags, holding times, and sequence-dependent setup times are taken into account. This problem is inspired by a real situation observed in a seamless rolled ring manufacturer. We propose a mixed integer linear programming (MILP) and a constraint programming (CP) models to represent the problem. Additionally, we develop a metaheuristic based on a Greedy Randomized Adaptive Search Procedure (GRASP) able to tackle efficiently large instances of the problem. The results show that CP outperforms the MILP and the proposed GRASP outperforms the CP when solving instances with more than 100 jobs.

This work introduces the sales force sizing problem with multi-period workload assignments, and service time windows. The motivation of the problem arises from a real life situation faced by a goods distribution company. The problem consists in determining the size of the sales force (i.e. the number of vendors to hire) and their daily schedules, within a planning horizon, to serve a set of customers in order to minimize the total nominal wage. There are different categories of customers and each customer has multiple time windows depending on the service day. Furthermore, the nominal wage of a hired vendor is determined by the most expensive category of the customers he serves. A mixed integer linear formulation and a heuristic are proposed for this problem. The performance of the heuristic algorithm is assessed over a set of instances adapted from literature. Computational results reveal the efficiency and scalability of the proposed procedure, providing a better tradeoff in terms of solution quality and running time than a commercial solver.