An integrated line planning and timetabling model is formulated with the objective of minimizing both user inconvenience and operational costs. User inconvenience is modeled as the total time ...passengers spend in a railway system, including waiting at origin and transfer stations. The model is solved using a cross-entropy metaheuristic. The line plan and timetable of Israel Railways is used as a benchmark. Using the same amount of resources, the average journey time of passengers is reduced by 20%.
Following a recent interest in sustainable scheduling under operational costs that vary over time, we study scheduling problems on a single machine under time-of-use electricity tariffs. We consider ...two main variants of the problem: cost minimization and profit maximization. In the cost minimization problem, the set of jobs to be processed is given, and the goal is to schedule all jobs within a planning horizon so as to minimize the total cost, while in the profit maximization problem, one needs to select a set of jobs to be processed such that the total profit is maximized. The general cases of the cost minimization and profit maximization problems in which preemptions are forbidden are strongly NP-hard. In this paper, we show that some special cases with identical processing times can be solved by efficient algorithms. In addition, we consider several extensions of the problems, including release times, due dates, and variable energy consumption.
Bike-sharing systems allow people to rent a bicycle at one of many automatic rental stations scattered around the city, use them for a short journey and return them at any station in the city. A ...crucial factor for the success of a bike-sharing system is its ability to meet the fluctuating demand for bicycles and for vacant lockers at each station. This is achieved by means of a repositioning operation, which consists of removing bicycles from some stations and transferring them to other stations, using a dedicated fleet of trucks. Operating such a fleet in a large bike-sharing system is an intricate problem consisting of decisions regarding the routes that the vehicles should follow and the number of bicycles that should be removed or placed at each station on each visit of the vehicles. In this paper, we present our modeling approach to the problem that generalizes existing routing models in the literature. This is done by introducing a unique convex objective function as well as time-related considerations. We present two mixed integer linear program formulations, discuss the assumptions associated with each, strengthen them by several valid inequalities and dominance rules, and compare their performances through an extensive numerical study. The results indicate that one of the formulations is very effective in obtaining high quality solutions to real life instances of the problem consisting of up to 104 stations and two vehicles. Finally, we draw insights on the characteristics of good solutions.
In this paper, we study an extension of the orienteering problem where travel times are random and time-dependent and service times are random. Additionally, the service at each selected customer is ...subject to a soft time window; that is, violation of the window is allowed but subject to a penalty that increases in the delay. A solution is a tour determined before the vehicle departs from the depot. The objective is to maximize the sum of the collected prizes net of the expected penalty. The randomness of the travel and service times is modeled by a set of scenarios based on historical data that can be collected from public geographical information services. We present an exact solution method for the problem based on a branch-and-bound algorithm enhanced by a local search procedure at the nodes. A numerical experiment demonstrates the merits of the proposed solution approach. This study is the first to consider an orienteering problem with stochastic travel times and soft time windows, which are more relevant than hard time windows in stochastic settings.
•A scenario based orienteering problem with time-dependent travel times.•An exact branch and bound algorithm enhanced by a local search heuristic.•A numerical experiment demonstrates the merits of the solution method.
We study the design of a network of automatic parcel lockers to facilitate the last-mile delivery of small parcels where parcels are delivered via service points near their recipients’ home ...addresses. The recipients then pick up their parcels at convenient times. This method saves a substantial share of the handling and transportation costs associated with the parcel delivery process. The deployment of such a network requires decisions regarding the location and capacity of the service points. If a parcel has to be delivered through a service point with no remaining capacity, the parcel is sent directly to the recipient’s address at a higher cost, or its delivery is postponed. Hence, there is a trade-off between the fixed setup cost, the variable operational cost, and the quality of the service. In this study, we take a bottom-up approach to the problem. We start by analyzing the dynamics of a single service point and show how to calculate a function that maps the parameters of its environment to the expected number of parcels that will be rejected from service or postponed. We then embed these functions in a mathematical model that optimizes the configuration of the network while considering the trade-offs described above.
•Characterizing the rejection and postponement in a parcel delivery service point.•Designing a network of automated parcel delivery service points.•Presenting a mathematical model that integrates the above characterization.•Demonstrating the solution using realistic instances based on large towns.
•Constraint programming (CP) is presented as modeling and solution approach for various assembly line balancing problems.•CP is demonstrated as generic and efficient modeling language for generalized ...assembly line design/balancing problems.•Performance evaluation shows that CP dominates MILP in most cases.
In this paper, the constraint programming (CP) approach is applied for the simple assembly line balancing problem (SALBP) as well as some of its generalizations. CP is a rich modeling language that enables the formulation of general combinatorial problems and is coupled with a strong set of solution methods that are available through general purpose solvers. The proposed formulations are conversions of well-known mixed integer programming (MILP) formulations to CP, along with a new set of constraints that helps the CP solver to converge faster. As a generic solution method, we compare its performance with the best known generic MILP formulations and show that it consistently outperforms MILP for medium to large problem instances. A comparison with SALOME, a well-known custom-made algorithm for solving the SALBP-1, shows that both approaches are capable of efficiently solving problems with up to 100 tasks. When 1000-task problems are concerned, SALOME provides better performance; however, CP can provide relatively good close to optimal solutions for multiple combinations of problem parameters. Finally, the generality of the CP approach is demonstrated by some adaptations of the proposed formulation to other variants of the assembly line balancing problem including the U-shaped assembly line balancing problem and the task assignment and equipment selection problem.
Rituximab targets the B-lymphocyte antigen CD20, providing pemphigus vulgaris patients with long-term remissions. However, the effects of repeated courses have not yet been established. This study ...aimed to evaluate the effect of repeated rituximab courses on remission length in pemphigus vulgaris. A total of 73 patients with pemphigus vulgaris treated with rituximab at a single centre were retrospectively analysed. Of 73 study participants (28 men, 45 women), 42 (58%) received a 2nd course of rituximab, 24 (33%) received a 3rd course, 4 (6%) received a 4th course, and one (1%) received a 5th course. Rituximab remained efficacious in each course, irrespective of previous treatments (complete remission 75-81%). Following the 2nd and 3rd courses, the results indicated longer remissions with reduced flare-ups, and the remission length increased with each subsequent course. We conclude that rituximab serves as a disease-modifying agent, notably for patients with moderate-to-severe pemphigus vulgaris.
The test collection problem, also known as the minimum test set problem or the minimum test cover problem, selects a minimal set of binary attributes by which it is possible to determine the state of ...a system. This problem commonly arises in applications such as medical diagnosis and fault detection in the design of monitoring systems. We generalize this problem by (i) allowing attributes to obtain arbitrary categorical values; (ii) allowing multiple attributes combinations to represent a single state of a system; and (iii) including a different cost for testing each attribute. The objective of the planer is to select a set of tests at a minimum cost that can determine the state of the system. To address this problem, we present an integer programming model and an effective exact solution method that uses the model’s unique structure to reduce its dimension. Using this method, large instances that could not be solved directly by a commercial solver can easily be solved. Our solution method was implemented and demonstrated to be superior to those described in previous studies when applied on two sets of benchmark instances from the literature. One dataset was adapted from the UCI repository and one was based on a realistic and large-scale sensor placement problem in urban water networks.
This paper presents a method for unsupervised classification of entities by a group of agents with unknown domains and levels of expertise. In contrast to the existing methods based on majority ...voting (“wisdom of the crowd”) and their extensions by expectation-maximization procedures, the suggested method first determines the levels of the agents’ expertise and then weights their opinions by their expertise level. In particular, we assume that agents will have relatively closer classifications in their field of expertise. Therefore, the expert agents are recognized by using a weighted Hamming distance between their classifications, and then the final classification of the group is determined from the agents’ classifications by expectation-maximization techniques, with preference to the recognized experts. The algorithm was verified and tested on simulated and real-world datasets and benchmarked against known existing algorithms. We show that such a method reduces incorrect classifications and effectively solves the problem of unsupervised collaborative classification under uncertainty, while outperforming other known methods.
PDF
