5TH INTERNATIONAL CONFERENCE ON APPLIED OPERATIONAL RESEARCH
29-31 JULY 2013, LISBON, PORTUGAL
APPLYING A SAVINGS ALGORITHM FOR SOLVING A RICH VEHICLE ROUTING PROBLEM IN A REAL URBAN CONTEXT
José Cáceres-Cruz, Daniel Riera, Roman Buil and Angel A. Juan
IN3-Computer Science Department, Open University of Catalonia, Barcelona, Spain
Department of Telecommunications and Systems Engineering, Universitat Autònoma de Barcelona, Bellaterra, Spain
Abstract. Nowadays urban transportation is a strategic domain for distribution companies. In academic literature, this problem is categorized as a Vehicle Routing Problem, a popular research stream that has undergone significant theoretical advances but has remained far from practice implementations. In fact, a general combinatorial routing problem has emerged as Rich Vehicle Routing Problem for considering problems inspired in real situations. Intra-urban distribution required a special combination of routing characteristics. In this study, we consider a routing problem with asymmetric cost matrix, heterogeneous fleet of vehicles, service times, limited routes length, open routes, and balanced loads in routes’ restrictions. Our objective function is to reduce the total traveling time. We present an algorithm based on a randomized Clarke & Wright’s Savings heuristic. We execute our algorithm with data from a company that distributes prepared food to more than 50 customers in Barcelona. The results reveal promising improvements in different scenarios.
A STOCHASTIC BIOLOGICALLY-INSPIRED METAHEURISTIC FOR MODELLING-TO-GENERATE-ALTERNATIVES
Julian Scott Yeomans, Raha Imanirad and Xin-She Yang
OMIS Area, Schulich School of Business, York University, Toronto, ON, Canada
School of Science and Technology, Middlesex University, London, UK
Abstract. In solving many “real world” decision-making applications, it is generally preferable to formulate several quantifiably good alternatives that provide numerous, distinct approaches to the problem. This is because policy formulation typically involves complex problems that are riddled with incongruent performance objectives and possess incompatible design requirements that can be very difficult – if not impossible – to incorporate at the time supporting decision models are constructed. By generating a set of maximally different solutions, it is believed that some of the dissimilar alternatives will provide unique perspectives that serve to satisfy the unmodelled characteristics. This maximally different solution creation approach is referred to as modelling-to-generate-alternatives (MGA). This paper provides a stochastic biologically-inspired metaheuristic simulation-optimization MGA method that can efficiently create multiple solution alternatives to problems containing significant stochastic uncertainties that satisfy required system performance criteria and yet are maximally different in their decision spaces. The efficacy of this stochastic MGA approach is demonstrated on a municipal solid waste case study. It is shown that this new computationally efficient algorithmic approach can simultaneously produce the desired number of maximally different solution alternatives in a single computational run of the procedure.
A VEHICLE ROUTING PROBLEM WITH A PREDEFINED CUSTOMER SEQUENCE, STOCHASTIC DEMANDS AND PENALTIES FOR UNSATISFIED DEMANDS
E.G. Kyriakidis and T.D. Dimitrakos
Department of Statistics, Athens University of Economics and Business, Greece
Department of Mathematics, University of the Aegean, Karlovassi, Samos, Greece
Abstract. We consider a stochastic vehicle routing problem in which the customers are served according to a predefined sequence and the demands of the customers are discrete random variables. It is assumed that a penalty cost is imposed if a customer’s demand is not satisfied or if it is satisfied partially. The objective is the determination of the policy that serves the customers with the minimum total expected cost. A suitable dynamic programming algorithm is developed for the determination of the optimal policy. It is proved that the optimal policy has a specific threshold-type structure.
A CONSTRUCTIVE HEURISTIC FOR PERMUTATION FLOW-SHOP SCHEDULING WITH THE MAKESPAN CRITERION: IN A PARTICULAR CASE WHERE THE SUM OF THE PROCESSING TIMES OF EACH JOB IS THE SAME ON EACH MACHINE
Tadbir Operational Research Group, Vancouver, BC Canada
Abstract. This paper describes an adaption of the fuzzy greedy heuristic (FGH) for the permutation flow-shop scheduling problem with the makespan criterion. In a particular case where the sum of the processing times of each job is the same on each machine, certain priority rule-based scheduling heuristics would assign the same priority to every job, and so in this situation, all possible permutations of the jobs would be equally likely to be selected by those heuristics. An efficient ranking method is proposed to prioritize the jobs in this particular case. Computational experiments using standard benchmark problems indicate that the proposed method is very efficient.
MODELING AND SOLVING A TIMETABLING PROBLEM CONSIDERING TIME WINDOWS AND CONSECUTIVE PERIODS
Diana Sánchez-Partida, José Luis Martínez-Flores and Elias Olivares-Benítez
UPAEP University, Puebla, México
Abstract. This paper presents a case study called UPAEP Timetabling. This problem arises in the allocation design of some or all of professors-courses-rooms-timeslots-groups variables, considering factors such as availability and capacity rooms. In the reviewed papers a general model that covers the requirements of any Institution have not been found due to operational rules set are determinants for constraints modeled; therefore normally a mathematical model is designed for each Institution. The proposed model is considered one of the most complete due to the kind of considerations in the moment of building the constraints. The model was validated at UPAEP University in the graduate education area, attempting to tackle a real-world problem, considering 85,223 variables, time windows of the professors, periods consecutive and capacity rooms, between other constraints. This document presents a mathematical model solved with commercial optimization software, which helped to found successfully the solution of the Timetabling Problem.
ON THE USE OF EXPERT OPINION TO CHARACTERISE THE JOINT BEHAVIOUR OF COMPETING RISKS IN INDUSTRIAL ACCELERATED LIFE TESTING
School of Statistics and Actuarial Science, University of the Witwatersrand, Johannesburg, South Africa
Abstract. Distribution identifiability issues arise quite naturally through competing risks in reliability. In particular, modeling and analysis of recurrent events which include the impact maintenance has on the lifetime distribution of repairable systems is an interesting practical application. This paper discusses the problem of modeling the joint behaviour of condition-based preventive maintenance (PM) and corrective maintenance (CM) in the competing risk context using copulas. Specifically, how expert judgement and accelerated life testing data can be used to estimate the copula dependence parameter and quantify its uncertainty through Monte-Carlo simulations is discussed.
AN O(T 3) ALGORITHM FOR THE CAPACITATED ECONOMIC LOT-SIZING PROBLEM WITH STATIONARY CAPACITIES AND CONCAVE COST FUNCTIONS WITH NON-SPECULATIVE MOTIVES
Pedro Piñeyro, Omar Viera and Héctor Cancela
Instituto de Computación, Facultad de Ingeniería, Universidad de la República, Montevideo, Uruguay
Abstract. We consider the capacitated economic lot-sizing problem (CLSP) with stationary capacities and concave cost functions with non-speculative motives. Under these assumptions we show that there is an optimal solution of the problem that is composed only by subplans that can be computed in linear time, which means that the problem can be solved in O(T 3) computation time.
MODELING SCHEDULED PATIENT PUNCTUALITY IN AN INFUSION CENTER
Seunggyun Cheong, Robert R. Bitmead and John Fontanesi
Australian Centre for Field Robotics, School of Aerospace, Mechanical and Mechatronic Engineering, the University of Sydney, Australia
Department of Mechanical & Aerospace Engineering, University of California, San Diego, La Jolla CA, USA
Center for Management Science in Health, University of California, San Diego, La Jolla CA, USA
Abstract. We introduce a new model structure for punctuality of scheduled patients. Each iteration of the model is a mixture of two exponential distributions, one for the punctuality of early-arriving patients and the other for late-arriving patients. Since patients’ earliness and lateness are treated separately, the models can capture different characteristics of each while many other model structures such as normal distributions treat them symmetrically. The new model structure is tested on data collected in a hospital infusion room and demonstrates quantifiably better performance than normal distribution fitting. The approaches are compared using two goodness-of-fit measures. Further, patient punctuality is shown to vary throughout a day depending on patients’ appointment times.
CLUSTERING OF CHARACTERISTICS OVER SPATIAL DATA
María Beatriz Bernábe Loranca, Rogelio González Velázquez, Elías Olivares Benitez, David Pinto Avendaño, José Luis Martínez Flores and J R Vanoye
Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación Puebla, México
Universidad Popular Autónoma del Estado de Puebla, Posgrado de Logística y Dirección de la cadena de Suministro, México
Abstract. For problems that require a spatial data analysis, the use of statistical methods that take into account the geographical location or work with the descriptive characteristics of the data in the aggregation process is frequent. To solve a clustering problem over population data, considering the quantitative values of the variables that describe the data is necessary. In these cases, it is assumed that said variables have a high correlation, which suggests a statistical analysis with the goal to achieve a consistent subset of these variables. Even when we count with a subset of variables without redundancies and due to fact that specific problems of population character demand a reduced number of variables, a procedure of data selection under criteria boundaries is important; in this way achieving a subset of variables that describe a specific population problem is possible. Two objects are generated from this procedure: an associated distances matrix formed with the chosen variables and a vector of census-descriptive variables, which are processed by a partitioning algorithm with homogeneity restrictions for a population variable of interest. The homogeneity in the clustering of Agebs (Basic Geo-statistical Areas) is very useful due to the fact that balanced groups are wanted, with respect to a value of a census variable that responds to a population problem. The objective of this work resides in solving the spatial partitioning problem for geographic data under homogeneity restrictions where the variables to consider are directly related with the censuses in Mexico. The Agebs have a geographical composition of latitude-longitude and a vector of 167 descriptive variables of census kind. The partitioning problem is of combinatory character, such that the use of Variable Neighborhood Search (VNS) has been necessary to optimize the objective function with the associated homogeneity restriction. Finally the results are presented for a homogeneous grouping case for economically inactive population.
Supply chain design and sustainability in the textile sector
R. Montemanni, C. Valeri, S. Nesic, L.M. Gambardella, M. Gioacchini, T. Fumagalli, H. Zeller, K. Meyer, M. Faist and A.E. Rizzoli
IDSIA – USI/SUPSI, Galleria 2, Manno, Switzerland
Hugo Boss Ticino SA, Via S. Apollonia 32, Coldrerio, Switzerland
EMPA, Ueberlandstrass 129, Duebendorf, Switzerland
Abstract. A project where optimization techniques and life cycle assessment methods are used to select a supply chain balancing economical and ecological factors is described. In particular, the optimization component will be analysed, modelled in mathematical terms and solved with methods previously appeared in the literature. The supply chain considered is the one of a top-brand firm in the textile sector.
A CUSTOMER SATISFACTION MODEL BASED ON FUZZY TOPSIS AND SERVQUAL METHODS
Melike Erdoğan, Özge Nalan Bilişik, İhsan Kaya and Hayri Baraçlı
Department of Industrial Engineering, Yildiz Technical University, Istanbul, Turkey
Abstract. Service quality is one of the most important factors that increases the use of public transportation system (PTS). Many problems such as traffic congestion, air and noise pollution, and energy consumption can be solved by improvements of service quality in PTS. In this paper, a hybrid methodology which consists of SERVQUAL (Service Quality) method that categorizes evaluation criteria and fuzzy TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) method that ranks alternatives is suggested for evaluation of service quality in PTS. The suggested methodology is applied in a real case that analyzes the PTS in Istanbul. As a result, the public transportation company that provides the highest customer satisfaction is identified.
A DYNAMIC PROGRAMMING APPROACH FOR PASSIVE OPTICAL NETWORK DESIGN IN TREE GRAPHS
Matthieu Chardy, Cédric Hervet and Dedy Bossia
Orange Labs, Issy-Les-Moulineaux, France
ENSTA/CEDRIC – Orange Labs, Issy-Les-Moulineaux, France
Institut Galilée – Université Paris 13, Villetaneuse, France
Abstract. The deployment of Fiber To The Home technologies is currently one of the most challenging issues for telecommunication operators. This paper focuses on the optimization of Passive Optical Network in tree graphs for which a dynamic programming solving approach is proposed. Tests performed on real-size instances prove the efficiency of this approach in comparison to integer linear programming based approaches.
AN ACCELERATION OF THE ALGORITHM FOR THE NURSE REROSTERING PROBLEM ON A GRAPHICS PROCESSING UNIT
Zdeněk Bäumelt, Jan Dvořák, Přemysl Šůcha and Zdeněk Hanzálek
Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Technicka 2, 166 27, Prague 6, Czech Republic
Abstract. This paper deals with the Nurse Rerostering Problem (NRRP) performed by a parallel algorithm on a Graphics Processing Unit (GPU). This problem is focused on rescheduling of human resources in healthcare, when a roster is disrupted by unexpected circumstances. Our aim is to resolve NRRP in a parallel way to shorten the needed computational time in comparison to already known algorithms. The design of the parallel algorithm is a non-trivial task and brings many crucial issues that are described in this paper, e.g. a thread mapping issue, the utilization of the memory and the minimization of the communication overhead between the PC and the GPU. These issues must be taken into account in order to achieve the expected speedup. Our algorithm is evaluated on the benchmark datasets and compared to the optimal results given by ILP. The part of the heterogeneous parallel algorithm running on the GPU was up to 6 times faster in comparison to its sequential version. In total, our parallel algorithm provides a speedup of 1.9 (2.5) times for the NRRP instances with 19 (32) nurses in comparison to the sequential algorithm.
ANALYZING THE BENEFITS OF MANURE SEPARATION USING MATHEMATICAL OPTIMIZATION
Hongbo Dong, Michael Ferris, Tom Cox and John Norman
University of Wisconsin-Madison, Madison, USA
Abstract. Optimization techniques are used extensively for strategic and operations planning in a large number of system engineering applications. We consider here the coupling of a crop planning, manure separation process and a nutrient management system for dairy farms. A nonlinear programming model is developed that determines optimal settings for each of these systems when coupled via a parametric herd size and farm layout. The model is at a full farm, or small farm system level. Numerical experiments are provided to illustrate the use of the model for exploring the interactions between environmental constraints and nutrient requirements and the logistic tradeoffs between manure processing and exogenous fertilization. Our results clearly show the benefits of manure separation in both of an environmental metric and an economic metric. Extensions that incorporate coupling of multiple optimization models are also discussed.
TOWARD CONSTRUCTING AN EFFECTIVE METHOD TO PREDICT OIL PRICES
Mamoon Alameen, Mohammed Abdul-Niby and Ali Radhi
Australian College of Kuwait, West Mishrif, Kuwait
Bahbahani Projects, Kuwait city, Kuwait
Abstract. As human civilizations advance, the dependence on oil grows rapidly. Predicting oil prices is a big challenge due to the importance of oil in effecting human life style. Unlike any other commodity, oil prices can’t be left to supply and demand factor only. The most popular approach to predict future oil prices is the statistical approach. The purpose of this study is to investigate the validity of taking a non statistical approach to predict oil prices.
SCHEDULING OF TRUCKS IN CROSS-DOCKING SYSTEMS: A HYBRID META-HEURISTIC ALGORITHM
B. Vahdani, R. Tavakkoli-Moghaddam, and S.M. Mousavi
Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
Abstract. Cross-docking is a logistics technique that minimizes the storage and order picking functions of a warehouse while still allowing it to serve its receiving and shipping functions. In this paper, we propose a novel hybrid meta-heuristic algorithm for solving scheduling trucks in cross-docking problems. This algorithm comprises three components: an initial population generation method based on ant colony optimization (ACO), simulated annealing (SA) as an evolutionary algorithm employs a certain probability to avoid becoming trapped in local optimum, and variable neighborhood search (VNS) that involves three local search procedures to improve the population. Moreover, to demonstrate the effectiveness of the proposed methods especially for large-sized problems, various test problems are solved. The computational results demonstrate that our proposed algorithm performs far better than those of Yu and Egbelu (2008).
A HYBRID GA FOR SIMULTANEOUSLY SCHEDULING AN FMC UNDER MULTIPLE OBJECTIVES
R. Tavakkoli-Moghaddam, M. Heydar and S.M. Mousavi
School of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
Department of Industrial and Manufacturing Engineering, University of Wisconsin, Milwaukee, USA
Young Researches Club, South Tehran Branch, Islamic Azad University, Tehran, Iran
Abstract. This paper solved a bi-objective scheduling problem in flexible manufacturing cell. The objectives considered are maximum completion time (makespan) and maximum tardiness. This class of scheduling problem, regardless of the criterion, belongs to the class of NP-hard problems. Therefore, exact methods are not able to solve practical cases of these types of problems. For this research, a new hybrid genetic algorithm (HGA) combined with four priority dispatching rules is proposed. For numerical study purposes different scheduling problems are generated and solved using the proposed HGA. The results show that the proposed approach performs well in terms of efficiency and quality of the solutions.
A SAMPLING-BASED APPROXIMATION OF THE OBJECTIVE FUNCTION OF THE ORIENTEERING PROBLEM WITH STOCHASTIC TRAVEL AND SERVICE TIMES
V. Papapanagiotou, D. Weyland, R. Montemanni and L.M. Gambardella
IDSIA – USI/SUPSI, Galleria 2, Manno, Switzerland
Abstract. In this paper, a variant of the orienteering problem in which the travel and service times are stochastic, is examined. Given a set of potential customers, a subset of them has to be selected to be serviced by the end of the day. Every time a delivery to a selected customer is fulfilled before the end of the day, a reward is received, otherwise, if the delivery is not completed, a penalty is incurred. The target is to maximise the expected income (rewards-penalties) of the company. The focus of this paper is to evaluate a sampling based way to approximate the objective function which is designed to be later embedded in metaheuristics.
SCHEDULING ELECTIVE PATIENT ADMISSIONS CONSIDERING ROOM ASSIGNMENT AND OPERATING THEATRE CAPACITY CONSTRAINTS
Wim Vancroonenburg, Patrick De Causmaecker, Frits Spieksma and Greet Vanden Berghe
CODeS, KAHO Sint-Lieven, Gent, Belgium
CODeS, KU Leuven KULAK, Kortrijk, Belgium
ORSTAT, Faculty of Economics and Business, KU Leuven, Leuven, Belgium
Abstract. The present contribution studies an elective patient admission scheduling problem considering both operating theatre capacity and room assignment constraints. The aim of the study is to determine how scheduling surgical and non-surgical admissions impacts room assignment issues at hospital wards, and how these can be avoided. We present a problem setting and the corresponding mathematical formulation as the basis of our study. First results will be presented at the conference.
A VARIABLE NEIGHBORHOOD SEARCH FOR THE SELECTIVE MULTI-COMPARTMENT VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
University of Economics, Prague, Department of Econometrics, Prague, Czech Republic
Abstract. This paper presents a generalization of the well-known vehicle routing problem with time windows (VRPTW). In the proposed selective multi-compartment VRPTW (SMCVRPTW) a limited number k of identic vehicles is available at a central depot to serve a set of customers. Each vehicle is equipped with m compartments of limited capacity which are dedicated to transport a particular type of a product. Each customer has a nonnegative demand for up to m products. Once a vehicle delivers a product p to a customer it collects a profit. A vehicle can visit a customer only within a given time window. The SMCVRPTW consist of determining a set of at most k routes starting and ending at the depot, satisfying all customer requests under capacity and time windows constraints such that the total collected profit is maximized. We present a variable neighborhood search algorithm to address the problem. The solution method is evaluated on standard VRPTW benchmarks enhanced with compartments and profit values.
IT'S TIME FOR A CHANGE TO BETTER UTILIZE RESOURCES IN HEALTHCARE
Tomas Eric Nordlander, Greet Vanden Berghe and Patrick Schittekat
SINTEF ICT, Department of Applied Mathematics, Oslo, Norway
CODeS, KAHO, Gent, Belgium
iMinds-ITEC-KU Leuven, Belgium
Abstract. To manage the rapid increase of hospital patients, there is an immediate need to improve efficiency of resource utilisation in healthcare. Adopting and applying traditional Operational Research techniques such as optimization is probably the most potent instrument to do this. However, to create a significant impact we need to dissolve the traditional problem partitions – formed by the limitation in processing power, outdated methods, and manual practice. Over the years, a substantial increase in processing power with significant improved methods has taken place. Still, the old partitions remain. We argue that it is high time to move to a more efficient partition that supports a better resource utilisation.
INTEGRATED PROJECT CONTROLS: USING OPERATIONS RESEARCH METHODS TO IMPROVE THE EFFICIENCY OF PROJECT CONTROL
Ghent University, Ghent, Belgium
Vlerick Business School, Belgium, Russia and China - and University College London, UK
Partner OR-AS (Operations Research - Applications and Solutions)
Abstract. Baseline scheduling and risk analysis go hand in hand and are crucial preparatory dimensions to provide information for the project control phase. One of the central lessons in training sessions to project managers is that scheduling without any form of risk management makes no sense since it then boils down to an academic and deterministic optimization exercise without much real life value. A project schedule is a dynamic instrument that needs to be adapted when necessary. Project managers have to deal with a continuous stream of unexpected events and need to take corrective actions to bring projects back on track or to update the initial estimates and expectations to a more realistic scenario. In that respect, a dynamic project schedule is the ideal tool to provide information and to support the corrective actions, and hence, the project baseline schedule acts as a point-of-reference to support these actions, rather than a forecast of the future that needs to be followed at all times.
PERFORMANCE ANALYSIS OF INVESTMENT STRATEGIES – PITFALLS AND SURPRISES
Peter Scholz and Ursula Walther
Hamburg School of Business Administration, Hamburg, Germany
Berlin School of Economics and Law, Berlin, Germany
Abstract. Active investment strategies are a subject of endless debates. Myriads of studies have been conducted to proof performance potential - or to reject previous studies due to flaws or misinterpretations. The presentation will address three specific aspects which often are disregarded when performance is measured. Firstly, we will discuss the role of backtests and show that this instrument – even when used carefully and skilled – may lead to biased and misleading results. Secondly, we give an example that the concepts of performance and forecast power must be strictly distinguished. Finally, we demonstrate that implementation details, while largely neglected, may strongly impact and bias a strategy’s performance.
OPTIMAL PORTFOLIO CHOICE WITH MULTIPLE BENCHMARKS
Frankfurt School of Finance and Management, Frankfurt, Germany
Abstract. The objective of many portfolio managers is to beat a specific benchmark. This benchmark is typically chosen to be the stock market. The performance of the fund is then compared with a performance of the benchmark, say a stock index SP500 for a fund that invest in US stocks. From the no arbitrage arguments, it is impossible to beat the stock index for sure, thus such an investment strategy can guarantee success only with a certain probability. The problem how to maximize the probability of beating a specific index by a certain percentage has already been widely studied in the previous literature. Thus we focus our attention to another drawback of such a strategy. The fund manager can still beat the stock index, but in the situation of a market downturn, his strategy can significantly underperform the money market, making the investor worse off in comparison to a conservative strategy of holding the currency. We can formulate the investment problem in the following way: we want the investment fund X to have at least a units of the stock market S and at least b units of the money market M at the end of the monitoring period T. Thus the objective is X_T > max(a S_T, b M_T). There is a region of values a and b such that this objective can be satisfied for sure and we find his set of feasible values in the geometric Brownian motion model. Certainly any values above 1 for both a and b are not feasible, this would create an arbitrage opportunity. We also find the trading strategy that would deliver the objective portfolio for any a and b in the feasible set. Since both values of a and b must be below 1, there is a possibility that the resulting portfolio would underperform both the stock and the money market. We explicitly compute this probability. As it turns out, this probability of underperformance of both benchmarks converges to zero as time goes to infinity. For the values of a and b outside of the feasible set, we can find the investment strategy that beats both benchmarks with the largest probability. In particular, we solve for the case a=b=1, which delivers the better of the two benchmarks. In the remaining part of the paper, we solve the problem of optimal investment for an arbitrary number of benchmarks, which can be for instance applied to foreign exchange markets.
© ORLab Analytics Inc