Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Robust optimization for resource-constrained project scheduling with uncertain activity durations ; ; Talla Nobibon, Fabrice in Flexible Services and Manufacturing Journal (2013), 25(1-2), The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence ... [more ▼] The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence associate probabilities with the possible scenarios. Our modeling techniques stem from robust optimization, which is a theoretical framework that enables the decision maker to produce solutions that will have a reasonably good objective value under any likely input data scenario. We develop and implement a scenario-relaxation algorithm and a scenario-relaxationbased heuristic. The first algorithm produces optimal solutions but requires excessive running times even for medium-sized instances; the second algorithm produces high-quality solutions for medium-sized instances and outperforms two benchmark heuristics. [less ▲] Detailed reference viewed: 74 (8 ULg)A Rich Vehicle Routing Problem with Multiple Trips and Driver Shifts Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande et al Conference (2012) This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The ... [more ▼] This study is concerned with a rich vehicle routing problem (RVRP) encountered at a Belgian transportation company in charge of servicing supermarkets and hypermarkets belonging to a franchise. The studied problem can be classified as a one-to-many-to-one pick-up and delivery problem, where there is a single depot from which all delivery customers are served and to which every pick-up demand must be carried back (Gutiérrez-Jarpa et al., 2010). The delivery and backhaul customers are considered to be two disjoint sets, where on a given route backhaul customers can be visited only after all delivery customers are served. Split deliveries and pick-ups are not allowed. The service at a customer must start within the given time window of the customer. However, it is not possible to serve a customer with every available vehicle, since the vehicles at the company’s disposal are of different types according to which the capacity changes. Therefore, our problem can be classified also as a heterogeneous fleet vehicle routing problem with customer-vehicle incompatibilities (Ceselli et al., 2009). The problem at hand requires that the same vehicle may be assigned to several routes, which leads to a multiple-trip RVRP. Furthermore, driver shifts are taken into account so that each vehicle of the fleet starts servicing the customers when the shift of the assigned driver starts. The shift duration is the same for all drivers. If the service of the vehicle exceeds SH, an overtime cost incurs to the transportation company. In such a case, a vehicle can be used during at most a fixed length of time. In addition to the vehicles of the company’s own fleet (i.e. internal vehicles), there is a possibility to request external vehicles for servicing some customers. External vehicles can be used for a fixed maximum amount of time and can start servicing customers at any desired time. A fixed reservation cost and distance and time based variable costs are incurred in the case of an external vehicle, while only distance based variable costs are incurred in the case of an internal vehicle. We employ a binary integer linear programming formulation in order to model our problem. The first constraint set ensures that each customer is visited at least once by either an internal or external vehicle. With the second constraint set, it is guaranteed that each internal vehicle is assigned to at most one tour. The last two constraint sets are the binary restrictions on the assignment variables. In order to solve the problem, we first relax the binary restrictions on the assignment variables and develop a column generation procedure, where we obtain two pricing problems, one for internal vehicles and the other one for external vehicles. The pricing problem of each internal vehicle can be formulated as an elementary shortest path problem with resource constraints, which can be solved using a dynamic programming algorithm based on a bounded bi-directional search (Righini and Salani, 2008). However, since an external vehicle can start the service at any point in time and is paid based on its total travel time, the second pricing algorithm has to take into account an infinite number of Pareto-optimal states (Liberatore et al., 2011). We discuss the efficient solution of the pricing subproblems and present preliminary computational results. [less ▲] Detailed reference viewed: 227 (6 ULg)The interval ordering problem ; ; et al in Discrete Applied Mathematics (2012) Detailed reference viewed: 11 (0 ULg)Complexity results and exact algorithms for robust knapsack problems Talla Nobibon, Fabrice ; Scientific conference (2011, March 04) Detailed reference viewed: 19 (0 ULg)Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles Talla Nobibon, Fabrice ; ; et al in INFORMS Journal on Computing (2011) We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption ... [more ▼] We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in microeconomics. We prove that the problem is NP-complete even for oriented graphs and argue that the existence of a constant-factor approximation algorithm is unlikely for an optimization version that maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms—namely, an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within a few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph more clearly than the CPU time of the two other procedures. For real-life instances, the integer-programming algorithm solves the largest instance in about a half hour, whereas the branch-and-check algorithm takes approximately 10 minutes and the backtracking algorithm less than 5 minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as a function of the number of arcs divided by the number of vertices. [less ▲] Detailed reference viewed: 39 (1 ULg)PROJECT SCHEDULING WITH MODULAR PROJECT COMPLETION ON A BOTTLENECK RESOURCE ; ; Talla Nobibon, Fabrice et al Report (2011) In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project ... [more ▼] In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project in order to maximize the expected profit when the activities have a probability of failure and when an activity’s failure can cause its module and thereby the overall project to fail. A module succeeds when at least one of its constituent activities is successfully executed. All activities are scheduled on a scarce resource that is modeled as a single machine. We describe various policy classes, establish the relationship between the classes, develop exact algorithms to optimize over two different classes (one dynamic program and one branch-and-bound algorithm), and examine the computational performance of the algorithms on two randomly generated instance sets. [less ▲] Detailed reference viewed: 20 (2 ULg)Robust maximum weighted independent-set problems on interval graphs Talla Nobibon, Fabrice ; Report (2011) We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate ... [more ▼] We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate solutions. For a discrete scenario set, we nd that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product, we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the rst objective function and that the scenario set can be reduced for the second objective function. [less ▲] Detailed reference viewed: 31 (1 ULg) |
||