A decision support system for the management of smart mobility services
Abstract
Nos dias que correm, a mobilidade assume especial importância no quotidiano das áreas metropolitanas em crescimento no país. . Com o notório crescimento das cidades, torna-se necessária e urgente uma transformação dos costumes e formas de mobilidade dentro das áreas urbanas, alterando as realidades aparentes que hoje conhecemos. Inseridos numa sociedade cada vez mais consciencializada e alerta para as questões ambientais, é essencial transportar esta mentalidade renovada para a resolução das problemáticas citadinas. Assim, o conceito de “Cidade Verde” levanta uma série de questões que exigem uma resposta eficaz para o bem-estar dos seus habitantes. Por entre as várias soluções apresentadas para estas patologias, uma das mais promissoras é, sem dúvida, o sistema de mobilidade partilhada. Pela sua dimensão, é pertinente expor o caso prático da cidade de Barcelona, em Espanha, explorando o seu sistema de partilha de scooters, um meio que adquire especial importância como meio de transporte urbano. Como qualquer sistema em constante aprimoramento, procura-se uma solução para a problemática da variação de procura, que apresenta oscilações constantes, tanto a nível temporal como geográfico, resultando na falta de veículos em algumas áreas e excesso noutras. Assim sendo, o rebalanceamento do sistema torna-se crucial para uma possível maximização na utilização de veículos, satisfazendo a procura e potenciando um aumento da sua utilização. No correr desta dissertação, foram estudados e utilizados vários métodos de otimização moderna (metaheurísticas) para a procura de soluções (sub)ótimas para o(s) percurso(s) a percorrer pelo(s) veículo(s) que executam a redistribuição das scooter/bicicletas pelas diversas áreas abrangidas pelo sistema de partilha. Deste modo, foi desenvolvido um sistema de apoio à decisão para satisfazer estas necessidades, garantindo ao utilizador toda a informação relevante para um trabalho mais eficiente e preciso.
Full text
University of Minho School of Engineering Department of Information Systems Guilherme Jesus Sousa Fernandes A Decision Support System for the Management of Smart Mobility Services January 2020
University of Minho School of Engineering Department of Information Systems Guilherme Jesus Sousa Fernandes A Decision Support System for the Management of Smart Mobility Services Master Dissertation Master Degree in Engineering and Management of Information Systems Supervisors Professor Dr. Paulo Cortez Dr. Nuno Oliveira January 2020
DIREITOS DE AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Atribuição-NãoComercial-CompartilhaIgual CC BY-NC SA https://creativecommons.org/licenses/by-nc-sa/4.0/
ACKNOWLEDGEMENTS This dissertation represents the culmination of 5 years of learning and continuous growth, widely reflected in this work. For this to take place, I always had the support of several people to whom I address my special gratitude: To Professor Dr. Paulo Cortez and Dr. Nuno Oliveira, for the generosity and trust when they guided me throughout this journey, and, above all, for the time spent in their orientation, which, despite the full schedule, was reflected in enriching moments and great learning. To my mother and brother, for the unconditional love and affection at all times. Thank you for your knowledge, for your confidence in me at the most difficult times, for your support in the hours of happiness and sadness that the writing of this thesis brought. To Bernardo, Felipe, João and Tiago, my closest university friends, for their friendship, companionship and help. Thank you for making this journey easier and for your help at all times, for the pleasure of sharing with you the joys and sorrows. To all my friends and colleagues who made this journey memorable: thank you for all the unforgettable moments. Thanks to my friends, from times when youth and innocence ruled life, Alexandre, Miguel, and Rui. Thank you for your patience and understanding in my absence. Thank you for your kindness, trust, and courage that you gave me to pursue and strive for my goals. To Daniel, my longtime friend who closely followed this journey, always with a friendly word to give me. For all the fellowship, friendship and patience, thank you. To my co-worker Pedro for the tips, advice and willingness to help. To Afonsina, for the second family that always accompanied me along this journey. Thank you for the companionship, friendship and alliance that always brightened my days and that will surely accompany me for the rest of my life. Finally, I would like to share the merits of this achievement with you, Joana. Because you have always walked by my side, been my safety net and best friend; half is yours and half is mine... half is you and half is me. You are the right probability in this Russian roulette life. As James LaBrie said in that song: ’Never in my dreams could I deserve to ever see a vision quite like her; then unexpectedly I’m taken by surprise; an angel just appeared before my eyes’. You really are my Arkenstone. ii
STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho.
RESUMO Nos dias que correm, a mobilidade assume especial importância no quotidiano das áreas metropolitanas em crescimento no país. . Com o notório crescimento das cidades, torna-se necessária e urgente uma transformação dos costumes e formas de mobilidade dentro das áreas urbanas, alterando as realidades aparentes que hoje conhecemos. Inseridos numa sociedade cada vez mais consciencializada e alerta para as questões ambientais, é essencial transportar esta mentalidade renovada para a resolução das problemáticas citadinas. Assim, o conceito de “Cidade Verde” levanta uma série de questões que exigem uma resposta eficaz para o bem-estar dos seus habitantes. Por entre as várias soluções apresentadas para estas patologias, uma das mais promissoras é, sem dúvida, o sistema de mobilidade partilhada. Pela sua dimensão, é pertinente expor o caso prático da cidade de Barcelona, em Espanha, explorando o seu sistema de partilha de scooters, um meio que adquire especial importância como meio de transporte urbano. Como qualquer sistema em constante aprimoramento, procura-se uma solução para a problemática da variação de procura, que apresenta oscilações constantes, tanto a nível temporal como geográfico, resultando na falta de veículos em algumas áreas e excesso noutras. Assim sendo, o rebalanceamento do sistema torna-se crucial para uma possível maximização na utilização de veículos, satisfazendo a procura e potenciando um aumento da sua utilização. No correr desta dissertação, foram estudados e utilizados vários métodos de otimização moderna (metaheurísticas) para a procura de soluções (sub)ótimas para o(s) percurso(s) a percorrer pelo(s) veículo(s) que executam a redistribuição das scooter/bicicletas pelas diversas áreas abrangidas pelo sistema de partilha. Deste modo, foi desenvolvido um sistema de apoio à decisão para satisfazer estas necessidades, garantindo ao utilizador toda a informação relevante para um trabalho mais eficiente e preciso. Palavras-Chave: Sistemas de Mobilidade Partilhada, Problema de Rebalancemanto de Bike Sharing, Sistemas de Apoio à Decisão, Otimização Moderna, Mobilidade como um Serviço. iv
ABSTRACT Nowadays, mobility is especially important in the daily life of the country growing metropolitan areas. With the increasing influx of people and development of these large cities, the reality of mobility that we know becomes increasingly unsustainable. Along with mobility, the environmental concerns are one of the main topics of discussion worldwide and the population is starting to act and change the way they live to find a more “green” and sustainable way of doing it. Several proposals have been put forward, trying to mitigate this issue and, one of the most promising is, undoubtedly, shared mobility systems. In this case study will be addressed the Barcelona scooter sharing system, characterized by its great size and importance as a mean of urban transport. One of the problems presented by these sharing services is that demand varies widely, both temporal and geographical. Thus, there are several cases where there is a lack of vehicles in some areas and an excess in others. The rebalancing of the system is crucial to maximize vehicle utilization and meet customer demand. In this thesis, several modern optimization methods (metaheuristics) were used to search for (sub)optimal solutions for the redistribution route(s). A decision support system was developed to meet this end, giving the end user relevant information for a more efficient and precise work. Keywords: Modern Optimization, Metaheuristics, Machine Learning, Neuroevolution, Online Learning, Mobile Advertising, Performance-based Advertising v
CONTENTS 1 introduction .................................... 1 1.1Problem Description and Proposed Solution . . . . . . . . . . . . . . . . 1 1.2ExpectedResults ................................ 2 1.3Bibliographic Research Strategy . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4DocumentOutline ............................... 4 2 literature review ................................ 5 2.1DecisionSupportSystems........................... 5 2.1.1Concept ................................. 5 2.1.2DSS asanUmbrellaTerm....................... 6 2.1.3DSS as a Specific Application . . . . . . . . . . . . . . . . . . . . . 6 2.1.4The Architecture of DSS ........................ 6 2.1.5Decision Support System Classification . . . . . . . . . . . . . . . 7 2.1.6The Decision Support System User . . . . . . . . . . . . . . . . . 8 2.2SmartMobility ................................. 8 2.2.1MobilityasaService.......................... 9 2.2.2Vehicle Sharing Systems . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3Operational Repositioning of Vehicles . . . . . . . . . . . . . . . . 11 2.2.3.1PredictedDemand...................... 11 2.2.4Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . 12 2.2.5Bike Sharing Rebalancing Problem . . . . . . . . . . . . . . . . . . 12 2.2.5.1StaticApproach ....................... 12 2.2.5.2DynamicApproach..................... 12 2.3OptimizationApproaches........................... 13 2.3.1Operational Research Methods . . . . . . . . . . . . . . . . . . . . 13 2.3.1.1LinearProgramming .................... 14 2.3.1.2Integer Programming . . . . . . . . . . . . . . . . . . . . 14 2.3.1.3Branch-and-bound...................... 14 2.3.1.4Branch-and-cut........................ 14 2.3.1.5Nonlinear Programming . . . . . . . . . . . . . . . . . . 14 2.3.2ModernOptimization ......................... 15 2.3.2.1LocalSearch ......................... 16 2.3.2.2Population-Based Search . . . . . . . . . . . . . . . . . . 18 2.4Decision Support Systems for Dynamic Vehicle Relocation . . . . . . . . 21 2.5Optimization of Dynamic Vehicle Relocation . . . . . . . . . . . . . . . . 25 vi
Contents vii 3 problem formalization ............................ 27 3.1ProblemDescription .............................. 27 3.1.1DescriptiveExample.......................... 27 3.1.2Problem Formulation and Definitions . . . . . . . . . . . . . . . . 29 4 development of the optimization system ................ 32 4.1Formulation ................................... 32 4.2ReadData .................................... 34 4.3Define Search Space and Solution Representation . . . . . . . . . . . . . 37 4.3.1Dimension................................ 38 4.3.2Bounds.................................. 39 4.4Search for (sub)Optimal Solution . . . . . . . . . . . . . . . . . . . . . . . 40 4.4.1Objective Goal Formulation . . . . . . . . . . . . . . . . . . . . . . 40 4.4.2Initial Solution and Population Definition . . . . . . . . . . . . . 41 4.4.2.1InitialSolution........................ 41 4.4.2.2InitialPopulation ...................... 44 4.4.3Change and Breeding (Genetic Operators) . . . . . . . . . . . . . 48 4.4.3.1Change ............................ 48 4.4.3.2Breeding (Genetic Operators) . . . . . . . . . . . . . . . 53 4.5Repair....................................... 54 4.6SaveResults ................................... 56 4.7StopCriteria................................... 57 4.8NewTrip..................................... 59 4.9OutputResults ................................. 60 5 experimental results and discussion .................. 61 5.1Solution Generation Approaches and Weight Experimentation . . . . . 61 5.1.1WeightExperimentation........................ 62 5.1.2Initial Solution/Population Experimentation . . . . . . . . . . . . 64 5.2SystemExperimentation............................ 66 5.3Discussion.................................... 68 5.3.1AuthorDefinedSolution ....................... 68 5.3.2SystemSolution............................. 71 6 conclusions and future work ........................ 74 6.1Synopsys..................................... 74 6.2Discussion.................................... 75 6.3FutureWork................................... 77 a system environment by scenario ...................... 86 a.1ScenárioI..................................... 86
LIST OF ABBREVIATIONS ACO Ant Colony Optimization ANN Artificial Neural Networks B&B Branch-and-bound B&C Branch-and-cut BRP Bike Sharing Rebalancing Problem BSS Bike Sharing System(s) DBMS Database Managements System DSS Decision Support Systems EA Evolutionary Algorithms FPT Full-Port Time GA Genetic Algorithms GUI Graphical User Interface HC Hill Climbing IP Integer Programming LP Linear Programming MaaS Mobility-as-a-Service MBMS Model Base Managements System MILP Mixed Integer Linear Programming MO Modern Optimization NP Nondeterministic Polynomial-time NR Number of Relocations OTS Optimization-trend-simulation PBS Population-Based Search PSO Particle Swarm Optimization SA Simulated Annealing SM Smart Mobility xiv
List of Abbreviations xv TS Tabu Search TSP Traveling Salesman Problem VRP Vehicle Routing Problem VSS Vehicle Sharing Systems ZVT Zero-Vehicle Time
1 INTRODUCTION 1.1 problem description and proposed solution This project was born due to a concern of CEiiA, a Centre of Engineering and Product Development that designs, develops and operates innovative products in the mobility industry. CEiiA is fully aware of the exponential growth of urban areas and their difficulties to maintain a fluid traffic jam and offer a smart and sustainable mobility paradigm to its dwellers. Along with mobility, the environmental concerns are one of the main topics of discussion worldwide and the population is starting to act and change the way they live to find a more “green” and sustainable way of doing it. Consequently, CEiiA saw an opportunity to make a difference and offered sharing services to the citizens of these overflowing urban areas. These services offer a mobility solution whereby vehicles (cars, bicycles, scooters, etc.) located at different stations across the urban areas, are available for shared use. These systems contribute to a more sustainable mobility in these areas, decreasing traffic and pollution caused by individual transportation. In these systems (sharing services), the demand is really dynamic and changes quickly, both at temporal and geographic level. There are many scenarios where there is a lack of vehicles in certain areas and an excess in others. A few challenges arise when setting up these systems to operate efficiently. Consequently, the decision makers need some sort of aid to give strength to their assumptions or give them some information that they were not taking into consideration. More than that, they need to optimize the way the system is currently working. With this in mind, this project comes to light, where the goal is to implement a decision support system to assist the management of smart mobility services. “If we have some concern about ’sustainability’ we need to anticipate what effects our use might have on future generations - and we have some clear indicators that there’s a problem.” — (Allwood and Cullen,2012) 1
1.2. Expected Results 2 1.2 expected results The main goal of this project is to develop a decision support system that optimizes the relocation operations in CEiiA’s vehicle sharing systems. Through modern optimization techniques, the operational repositioning of the vehicles will be optimized. The system should: • deliver the route(s) that the relocation vehicle(s) should take to rebalance the system; • detail the outcome (distance and time) to the user; and • adapt to new information (constraints and assets). 1.3 bibliographic research strategy Every scientific development starts with a proper scientific research, in which the developer aims to learn about fundamental concepts of the research theme and discover its state of the art. Therefore, the researcher needs to follow a search methodology to find the documentation to support the outcome. To that end, the investigation process initiated with the investigation of the most important concepts and related keywords and then went to more specific and practical case studies. A few search platforms were defined as essential to this step: Google Scholar,Web of Science,ScienceDirect and ResearchGate. Aside from the platforms, the keywords choice to unveil the most relevant documents was also truly important. “Vehicle Routing Problem (VRP)” was the first description of the project that was found. Since that early definition, others started to appear, as “Vehicle Sharing Systems (VSS)” or “Bike Sharing Rebalancing Problem (BRP)". All of these are important and slightly different concepts. The foundation concepts of this project were also key-concepts to be defined and learned: “Decision Support Systems (DSS)”, “Smart Mobility (SM)”, “Mobility-as-a-Service (MaaS)” and “Modern Optimization (MO)”. As expected, several irrelevant articles and books resulted from the search queries. Thus, a filtering criterion was adopted, as shown in Figure 1, to select the documents to build the groundwork for this project. All selected works were manually inspected, in terms of their titles and abstracts.
1.3. Bibliographic Research Strategy 3 Research Relevant Title? Unrelevant reading Read abstract Document in a recognized platform? Document with many quotations? Relevant bstract? Read sections headlines Related? Read introduction and conclusion Search keywords Read the respective paragraph Relevant? Unnecessary further reading Necessary reading no yes yes no yes no yes no no yes yes Figure 1: Literature selection process
1.4. Document Outline 4 1.4 document outline This document is organized in six chapters which are structured as follows: Chapter 1 is the introduction where the problem is described and a solution is proposed; expected results are outlined and the bibliographic research strategy is depicted. The literature review is presented in Chapter 2. It has six subchapters: Decision Support Systems;Smart Mobility; Optimization Approaches; Decision Support Systems for Dynamic Vehicle Relocation; Optimization of Dynamic Vehicle Relocation. Decision Support Systems subchapter approaches the basic concepts of DSS; Smart Mobility covers the concepts of Smart Mobility,Mobility-as-a-Service, Operational Repositioning of Vehicles and the well-known Bike Sharing Rebalancing Problem. Optimization Approaches presents the main differences between the operational research and modern optimization methodologies, detailing some of the most popular algorithms used in the area. Decision Support Systems for Dynamic Vehicle Relocation document some of the state of the art DSS developments in vehicle routing problems, with particular attention to vehicle relocation cases. Optimization of Dynamic Vehicle Relocation subchapter states some of the most common algorithms in the area. Then, Chapter 3formalizes the problem and specifies the environment that underpins the system development. In Chapter 4the implementation construction and the flow of the system are detailed, presenting a step by step design. The execution of the algorithms and their behavior in the search for the sub(optimal) solution is also specified. Chapter 5 demonstrates and discusses the experimental results and Chapter 6summarizes the system conception with closing statements and concludes with recommendations of potential future work.
2 LITERATURE REVIEW This chapter covers the theoretical background associated with this thesis: “A Decision Support System for the Management of Smart Mobility Services”. The first section (Section 2.1) provides an overview of what a Decision Support System is, and which benefits business managers can expect with his adoption. The next section (Section 2.2)– covers the rising interest of Mobility-as-a-Service in urban areas. Then, Section 2.3 describes the most technical aspects of the development of the project itself, presenting an introduction of modern optimization concepts and some of the algorithms used in operational research ands metaheuristics areas, within this project context. Sections 2.4 and 2.5 we address some real cases examples, proving a practical perception of success cases to be considered when designing the development phase. 2.1 decision support systems This section introduces the concept of Decision Support Systems (DSS), presenting definitions and contextualization about the project. It was strongly influenced by the book Decision Support and Business Intelligence Systems, 9th edition (Turban et al.,2010), a reference book in the area. We note that the term DSS is used in this work to refer to both its plural and singular forms. 2.1.1Concept Decision Support Systems (DSS) does not have a universally accepted definition among the experts of the area for it is a content-free expression1. However, we are going to see some of the early definitions and relevant concepts that characterize it. In the early ’70s, Scott Mortin defined DSS as an “interactive computer-based systems which help decision makers utilize data and models to solve unstructured problems”. A few years later Keen and Scott-Morton (1978) came with another classic DSS definition that is still employed nowadays: “Decision support systems couple the intellectual resources 1Has different meaning to different people. 5
2.1. Decision Support Systems 6 of individuals with the capabilities of the computer to improve the quality of decisions. It is a computer-based support system for management decision makers who deal with semistructured problems." By these definitions, we can perceive a DSS as a computer-based system intended to support managers in a decision situation. It should be seen as a way to extend decision makers capabilities and never as a machine with the intent to replace people’s judgment. 2.1.2DSS as an Umbrella Term As previously said, DSS definitions are open to several interpretations. DSS can also be used as an umbrella term. By this characterization, DSS encompasses separate support systems within an organization, like marketing, finance, accounting, production, and many other systems. 2.1.3DSS as a Specific Application Although DSS is usually applied to refer the umbrella term, some use it to refer to the application itself. Most of the times, DSS are developed to evaluate opportunities or and support the solution of a specific problem or set of them. Usually, DSS have their own databases to support the storage of the data; provide a straightforward user interface; support all decision-making phases and can be used by a single user on a personal computer (PC) or by many on a Web-based interface. 2.1.4The Architecture of DSS Typically deployed online, DSS have three main components: data, models and a user interface. There is still a fourth, which is an optional one - Knowledge. The individuality of the support provided, and overall capabilities of the system are defined by the way these components are assembled (typically via internet). This suggests that a DSS application can incorporate a data management subsystem, a model management subsystem, a user interface subsystem, and a knowledge-based management subsystem. Data Management Subsystem All the relevant data for the DSS to operate is stored in a database and managed by Database Managements System (DBMS) software. Model Management Subsystem This subsystem is a software package which contains statistical, financial and other quantitative modelsthat provide analytical capabilities and appropriate software management. This software is generally called a Model Base Managements System (MBMS)
2.1. Decision Support Systems 7 Figure 2: High-level architecture of a DSS, adapted from (Turban et al.,2010) User Interface Subsystem The final user is also considered a part of the system. He communicates with the DSS through the user interface subsystem. Most of Decision Support Systems provide a Graphical User Interface (GUI) over a Web Browser. Knowledge-Based Management Subsystem ADSS must include the three components described until now - DBMS,MBMS, and GUI. The knowledge-based management subsystem is nonmandatory, but it can grant intelligence and other benefits to the system. This subsystem can act as an independent component of the system or support the other three. This knowledge is usually granted by Web Servers. Figure 3: Schematic view of a DSS, adapted from (Turban et al.,2010) 2.1.5Decision Support System Classification The expected outcome of this project is a DSS that, with the proper input, should give the best answer to the final user. Therefore, the emphasis of this system will be optimization. This purpose fits in the Model-Driven DSS classification. The focus of such systems lays on optimizing one or more objectives, like increase profit, reduce costs, etc.
2.2. Smart Mobility 8 2.1.6The Decision Support System User This project intends to improve Decision Support Systems of CEiiA’s sharing services by proposing better routes for their maintenance operations. The main objective is to provide DSS users with real-time information that permits more efficient maintenance operations; not only for the rebalancing of the system but also for the preservation of the vehicles functionality (e.g., battery change). 2.2 smart mobility Smart Mobility is a new concept that came in the last few years with the growth of internet of things applications and other emerging technologies. Marked by the promise of environmental change and new mobility solutions, this key component to urban transportations change aims to reduce car use and related problems, like traffic congestion, crashes, poor air quality and more (Docherty,2018). Private vehicle ownership is still the solution adopted by the great majority of the population to address their everyday mobility purposes. A massive adoption of the Mobilityas-a-Service (MaaS) paradigm requires a mindset shift from vehicle ownership to vehicle ‘usership’ (Wockatz and Schartau,2015). Smart Mobility acceptance and implementation can change the way we live in society, avoiding much of the waste, pollution and environmental degradation (Docherty,2018). Nowadays, we can already see the numbers and the change associated with this shift. In 2014, car sharing systems had almost 5 million members and 92000 vehicles worldwide (Vine et al.,2014). The International Transport Forum (ITF-CPB,2017) went even further when predicted that an integrated system of on-demand taxis and taxi buses in a rail system in Lisbon, Portugal could achieve a 44% reduction in peak vehicle kilometres and 53% reduction in CO2emissions in the city, and release fully 95% of parking spaces for other public uses. Hietanen (2014) sets out his view of future mobility as seeing “the whole transport sector as a co-operative, interconnected ecosystem, providing services reflecting the needs of customers”. The boundaries between different transport modes are blurred or disappeared completely. The ecosystem consists of transport infrastructure, transportation services, transport information and payment services.
2.3. Optimization Approaches 15 2.3.2Modern Optimization The discipline of Operational Research produced many techniques to address multiple realworld problems. These optimization techniques are often referred to as ’classic’ techniques (Michalewicz,2007). On the other hand, Modern Optimization8(Michalewicz et al.,2006) methods are appropriate to a wide range of distinct problems, with no need for extensive domain knowledge, or problems for which no specific optimization algorithm has been developed, in contrast with these classical techniques (Cortez,2014). Another differentiating aspect is that Modern Optimization does not assure that the best possible solution (optimal) is always found but, instead, with reasonable use of computational resources, a high-quality solution (sub-optimal) is determined. Once the objective of the optimization9is clear and defined, only two details need to be specified: The representation of the solution and the evaluation function. The representation of the solution is a predominant specification. It will determine the search space and its scope and, if we do not select the correct domain, in the beginning, we might end up digging holes in a territory with no gold. The next thing to do is design an evaluation function that allows the algorithms to evaluate how good a solution is and compare the quality of different ones (e.g., Formalization 1). A general constrained optimization problem can be formally stated as follows (Rao,2009): minimize Xf(X) subject to gj(X)≤0, j=1, . . . , m hj(X) = 0, j=1, . . . , p (1) where Xis an n-dimensional vector called the design vector, f(X)is the objective function and g(X)and h(X)are constraints. The components of the Xvector are the design or decision variables xi,i=1, 2, . . . , n. Finally, the set of all possible solutions define the search space. After clarifying the core aspects of modern optimization, their most popular algorithms (related to this project) are next detailed. The blueprint of the algorithms was based on Cortez (2014) and Blum and Roli (2003). 8Also known as “modern heuristics” (Michalewicz and Fogel,2004) and “metaheuristics” (Luke,2013) 9Minimization/maximization expression, regarding the domain constraints.
2.3. Optimization Approaches 16 2.3.2.1Local Search Also known as single-state search, local search optimization algorithms concentrate in a local neighborhood of a given initial solution, generating new solutions from current ones. All local optimization techniques use iterative improvement (Michalewicz,2007). Hill Climbing Hill Climbing (HC) is a local optimization technique that hikes up and down a hill until a local optimum is obtained. It starts by considering a single current solution in the search space and comparing it to a new one from its neighborhood. If that solution has a better fit to the problem than the current one, this one starts to be considered the best solution and the former is forgotten. Otherwise, nothing happens and another neighbor is selected, repeating the procedure. The procedure ends when no further improvements are feasible, or the designated time runs out (Michalewicz,2007). Algorithm 1Hill Climbing Input: s(initial solution), f(evaluation function), . . . (other parameters) while termination conditions not met do .E.g. maximum number of iterations s0←change(s, ...).Pick a solution from sneighborhood s←best(s,s0,f).Select best solution for next iteration end while Output: s Simulated Annealing In the ’80s, a variation of the Hill Climbing was proposed: Simulated Annealing (SA). Inspired by the annealing phenomenon of metallurgy, SA considers a control parameter T (commonly referred to as temperature) to decide whether to accept an inferior solution or not10. The parameter T starts the execution with high values (randomizing the search) and then, gradually decreases. Towards the end, the T value is quite low, making the algorithm behave like Hill Climbing. Algorithm 2Simulated Annealing Input: s(initial solution), T(initial temperature), f(evaluation function), . . . (other parameters) while termination conditions not met do for iiterations do .Iterate itimes for each T s0←change(s, ...).Pick a solution from sneighborhood if s0=best(s,s0,f)then s←s0.Select best solution for next iteration else s←accept(T,s0,s).accept worse solution end if end for T←cooldown(T).Cooling schedule end while Output: s 10 The higher the temperature (T value), the higher the probability to accept an inadequate solution is.
2.3. Optimization Approaches 17 Tabu search Tabu Search (TS) is a variation of Hill Climbing (Cortez,2014). Its purpose is simple - prevent an iteration of the search that had already been performed (during a specified amount of iterations). The way that this happens is also simple. The algorithm includes a ’memory’ (tabu list of length L) that forces the search to move to unexplored search space, preventing it from being stuck in a local optimum. The memory stores the most recent solutions and does not let the algorithm ’visit’ them in the next iterations, avoiding unnecessary searches. After the number of iterations surpasses the length Lof the memory, the positions turn, once again, available. Algorithm 3Tabu Search Input: s(initial solution), f(evaluation function), . . . (other parameters) list ← {} .Tabu list while termination conditions not met do s0←change(s,list, ...).Pick a solution from sneighborhood, not in list if s0=best(s,s0,f)then update(list,s).Update list s←s0.Select best solution for next iteration else update(list,s0).Update list end if end while Output: s
2.3. Optimization Approaches 18 2.3.2.2Population-Based Search Another interesting class of search methods is the Population-Based Search (PBS). Instead of using a single search point, PBS uses a set of feasible solutions. Because of this, these methods tend to avoid being stuck at local minimums by easily locating worthy regions of the search space (Michalewicz and Fogel,2004).The usage of more computational power can be justified by the diversity of solutions that can be found, using these methods. Most population-based methods steal concepts from biology (Luke,2013). Genetic and Evolutionary Algorithms Based on evolution theory, Genetic Algorithms (GA)11 follow the principle in which only the fittest entities survive. More recently, the term Evolutionary Algorithms (EA) was adopted to address genetic algorithm variants, which include real value representations and flexible genetic operators (Michalewicz,1996). In a simple way, following the biological terminology associated (Luke,2013), the behavior of the algorithms goes something like this: It starts with an initial generation of candidate solutions and then generates new ones (breeding) through genetic operators like crossover and mutation.Crossover generates children through a combination of two or more parent solutions, while mutation performs a small change to an individual (Cortez,2014). Algorithm 4Evolutionary Algorithms Input: f(evaluation function), . . . (other parameters) P←initialize(. . .).Random (or not) initial population while termination conditions not met do eval(P).Evaluate P individuals p←select_parents(P).Select a set of parents from P p0←crossover(p).Create offspring p00 ←mutation(p0).Apply mutations to some children eval(p00).Evaluate new individuals P←select(p∪p00).Set next population end while Output: P 11 Proposed John Holland at the University of Michigan in the 1970s (Luke,2013).
2.3. Optimization Approaches 19 Swarm Intelligence With a family of algorithms like Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO),Swarm Intelligence is inspired by the swarm behavior manifested by several animals, like ants, bees, and others (Cortez,2014). The essence of Swarm Intelligence lays on the self-organized behavior that the agents’ population presents (Michalewicz,2007). particle swarm optimization is a stochastic12 optimization technique that is essentially a form of guided mutation (Luke,2013). Unlike other population-based methods, PSO does not focus on expanding the population but in its preservation. When changes in the search space are detected, the population members are tweaked. In other words, candidate solutions are mutated towards the best solution (the guided mutation moves the particles in the search space). Algorithm 5Particle Swarm Optimization Input: f(evaluation function), . . . (other parameters) Population ←initialize_population() .Initialize population Best ←best(P,f).Best particle while termination conditions not met do for p∈Population do .Iterate over all particles s←move(s, ...).Update particle’s position s←adjust(s, ...).adjust s position (if outside bounds) if f(s)<f(p)then p←s.Update previous best end if if f(s)<f(B)then p←s.Update best value end if end for end while Output: B 12 Something that was randomly determined.
2.3. Optimization Approaches 20 ant colony is an algorithm inspired by real colonies of ants, which pour pheromone on the ground to influence the behavior of other ants; the greater the amount of pheromone on a particular path, higher the probability that other ants will select it. In these systems, the pheromone levels guide the creation of new solutions (Michalewicz,2007). Algorithm 6Ant Colony Optimization Input: f(evaluation function) initialize_pheromone() .Initialize pheromone levels while termination conditions not met do for ant ∈Colony do .Iterate over all ants s←constructSolution() .Construct solution f(s).Evaluate s end for update_pheromone() .Update pheromone levels end while Output: s
2.4. Decision Support Systems for Dynamic Vehicle Relocation 21 2.4 decision support systems for dynamic vehicle relocation As we saw, these sharing services need some sort of system that offer some aid to the management when it comes to decision making. To this day, different Decision Support Systems were developed to help these managers, allowing them to have a clearer view of the day to day scenarios and provide information about what repercussions each decision should lead. Some real-world examples are presented in the next section. Kek et al. (2009) present a three-phase optimization-trend-simulation (OTS) decision support system to help car sharing operators determine a set of near-optimal manpower and operating parameters for the vehicle relocation problem. This DSS was tested on real-world operational data from a car sharing company in Singapore. The results are fascinating. They suggest that the manpower recommended by the system lead to a cut in staff cost of 50%, a reduction in zero-vehicle-time ranging between 4.6% and 13.0% and a contraction in the number of relocations between 37.1% and 41.1%. The structure of this approach is presented in Figure 4. Figure 4: Structure of the three-phase OTS DSS, adapted from (Kek et al.,2009) The first phase of the OTS is an Optimizer. It receives, as input from the car sharing system, characteristics such as the number of parking stalls, staff costs, vehicle relocation costs; then proceeds to determine the resource allocation that minimizes the cost, displaying the optimized staff needs and activities, relocations and the number of vehicles at the stations at each time. Trend Filter, the second phase, receives the output from the Optimizer and ’filters’ them through heuristics. The expected output is a set of recommended operating parameters. The third and last phase of OTS evaluates the effectiveness of the recommended parameters using three performance indicators - ZVT (Zero-Vehicle Time), FPT (Full-Port Time) and NR (Number of Relocations). We note that in this work, when ZVT occurs at a station, the station has no available vehicles to satisfy the demand. When FPT occurs, the station has no empty parking stalls and users want to return the vehicles to that station (not being able to do so). A greater value of NR means a higher cost of vehicle relocation operations and, both ZVT and FPT reduce the attractiveness of the carsharing system to users. Consequently, for an optimal performance of the system, the values for ZVT,FPT and NR should all be minimized (close to zero). The implementation of OTS presented interesting results. In Figure 5we can see that all the performance indicators are either maintained or reduced. The most relevant value is the NR.NR levels dropped to an exciting 41.1%.
2.4. Decision Support Systems for Dynamic Vehicle Relocation 22 Figure 5: Comparison of OTS against base model, adapted from (Kek et al.,2009) From the values shown in Table 1, we can see the performance improvement when compared to the base model. Table 1: Percentage improvement in permonce indicator of OTS, adapted from (Kek et al.,2009) Vehicle to Trip-Station Improvements Ratio dfgwZVT dffwFPT dfwNR 0.03 4.6 0.0 41.1 0.07 6.0 8.1 38.0 0.12 11.2 0.0 37.1 0.21 13.0 71.3 0.0 In another example, Caggiani and Ottomanelli (2012) developed a flexible fuzzy DSS (based on a Fuzzy Inference System13) for the vehicles relocation in a bike sharing system. The goal was to determine the optimal repositioning flows, time intervals and distribution patterns that would minimize the redistribution costs and assure user satisfaction. The system starts to predict future demand among stations, basing the forecast demand method on Artificial Neural Networks (ANN) and Fuzzy Logic14. The Neural Net translates the spatio-temporal variation of requests, giving the user important feedback about the vehicle usage for that day or time period. Being based on fuzzy logic suggests that the result can be better than a traditional one, especially when dealing with uncertain, imprecise or ambiguous environment. 13 A fuzzy inference system is a system that uses fuzzy set theory to map inputs to outputs. 14 Fuzzy logic is an approach based on ’degrees of truth’ rather than the usual ’true or false’ logic on which the modern computer is based.
2.4. Decision Support Systems for Dynamic Vehicle Relocation 23 When the demand is known, the system needs to be rebalanced. The relocation paths are calculated by solving the well-known TSP, formulated as fixed-point Non-Linear Integer Optimization. The solution algorithm is based on a Branch-and-bound algorithm. The proposed DSS leads to a diminution of lost users, increasing their probability of finding available bikes or free slots. The operation of the system was only simulated and not deployed, but easily could be extended to wider and real sized systems. Many were the initiatives that emerged in the last few years, regarding vehicle routing problems. These examples were detailed because of the similarities to this project, but we are going to see many other important developments in this specific area. Not all of them are about Decision Support Systems per se, but the fundamentals of redistribution systems are covered. In the late ‘90s, Dror et al. (1998) proposed that a fleet of electric vehicles relocation should be made by a fleet of capacitated tow trucks. Two decades after, we are still making progress in this area, that is more actual than never. A year later, Barth and Todd (1999) simulated a rebalancing system and showed that the vehicle relocation is minimized when 18-24 vehicles are available for every 100 users. A few years later, Wang et al. (2010) presented a forecast-based relocation model that showed an improvement in the overall efficiency of the system. Correia and Antunes (2012) formulated a Mixed Integer Linear Programming (MILP) strategy to optimize the depot location in a one-way carsharing system and Boyacı et al. (2015) proposed a multi-objective MILP to develop one with an electric fleet. The benefit of sharing systems in coexistence with other networks such (as public transportation) was studied by Chow and Sayarshad (2014) and, in the same year, Nourinejad and Roorda (2014), by taking the user needs and individuality into account (departure, arrival and request time), defined a better model that can be used, not just as a DSS for optimal relocation operations, but also as a strategic decision-making aiding tool to find an optimal fleet size. In round-trip systems, the requirements are slightly different. The fact that the users have to return the vehicles to the departure location forces the system to have a higher fleet size (Nourinejad and Roorda,2015). When the system has uncertain requirements, some adjustments need to be made. Studies were made and articles were published to address these particular cases. Fan et al. (2008) and Nair and Miller-Hooks (2011) developed different models to address these issues. The first had the objective of maximizing revenues and minimizing relocation costs; the second wanted to minimize the cost of vehicle relocation. When it comes to bike sharing systems, some things are not the same. The literature covers that as well. Some examples will be following presented.
2.4. Decision Support Systems for Dynamic Vehicle Relocation 24 Froehlicj et al. (2008), using data from a Bike Sharing System(s) in Barcelona (Spain), tested a few predictive techniques to forecast the demand. The results present an astonishing average error of 8% over all days. Another experiment, led by Borgnat et al. (2011), through data from BSS on Lyon (France), predicted hourly rental of vehicles. Many different approaches were used in the last few years to predict user behavior and habits towards demand. Hemdersom and Fishman (2013) predicted departures and arrivals from customers on time window of 1 hour and the expectation of stations occupancy. The model was tested on the BSS from Chicago (EUA). Borgnat et al. (2011) and Caggiani and Ottomanelli (2013) went the extra mile and included weather and holidays in their studies. With that detail, they were able to improve their predictions accuracy in more than 50%. Predictions of users demand only give companies the knowledge to design better systems. The real value emerges when inventory and routing problems start to take part in the equation. Some authors described their work with these aspects. Caggiani and Ottomanelli (2013) proposed a DSS that, based on the user demand prediction, minimized the repositioning costs. Schuijbroek et al. (2013) also address both problems, combining them into a single framework. To summarize, through historical data, estimate optimal inventory levels, which serve as a base to the routing problem, minimizing the distance to travel. The model performance was tested on systems from Boston and Washington (USA). A solution was identified within one or two minutes (better than other often-used formulations after two hours). Regue and Recker (2014) proposed to find the optimal inventory levels at each station and the optimal routes for the repositioning vehicles to redistribute bikes through a BSS. They combined different datasets to foresee future station inventory levels. Based on the results, a stochastic linear integer problem was resolved to determine the estimated number of bikes required at each station. As we can see, this area has experienced a boom in the last few years derived to the necessities of today’s society.
3.1. Problem Description 31 Figure 9: Example of a feasible folution
4 DEVELOPMENT OF THE OPTIMIZATION SYSTEM 4.1 formulation This project attempts to address the lack of real, dynamic and adaptable solutions to solve this problem; adaptable to the size of the available truck fleet, their features, environment characteristics, and business rules. The system should be easily adjusted to the different types of vehicles to be transported and not attached to a specific type. Despite several studies and papers on this subject, there is no holistic approach that contemplates the endto-end process, developed and planned for a mild and effective implementation. The fact that the need for such systems is more popular than ever raises the need for a solution that meets the constraints of most BSS businesses in major cities. There is an obvious urgency for such solutions to cease to be the focus of academic studies alone and focus on developing cohesive and robust solutions. The project will compare the performance of algorithms that follow different approaches and converge to a solution that can address the day to day business requirements. This is a a problem that can either be solved by a single trip, carried by a single truck, or by ttrips, performed by mvehicles. The final solution will be represented by a matrix in which each row describes a trip. The solution should look like this: sol = l11 l12 . . . l1n l21 l22 . . . l2n . . .. . ..... . . lt1lt2. . . ltn Where trepresents each trip and nthe station visited, lis the load that the truck has when leaving each station n. To explain the development and associated logic of the system, we are going to follow the already listed example (see Chapter 3.1). The system can be represented by the flow represented in Figure 10. Each step of the flow is explained in the following sections. 32
4.1. Formulation 33 Read Data Define Search Space outer config variables Search for (sub)optimal Solution Repair Save Results New Trip Stop Criteria? Output Results no yes Figure 10: Optimization system flow
4.2. Read Data 34 4.2 read data In general terms, the first phase of the system is the building of its infrastructure and the loading of the specifications in which the rebalacing optimization is going to be built upon. Global variables like stations demand, distance between them, available fleet and truck atributtes are loaded. The description of the variables are presented in Tables 5and 6. Table 5: Data provided Name Extension Purpose Description relocations .csv Necessities to be met A dataset with 3 columns and 8267 rows, each one of them expressing the necessities associated with a particular station, at a particular time. Example: Table 7 distances .csv Distances between stations A dataset with 264 columns and 264 rows, each one of them representing the distance (meters) between areas. Example: Table 8 areas .csv lat e lon of each station A dataset with 3 columns and 264 rows, each one representing the latitude and longitude of each area’s centroid. Example: Table 27 Table 6: User defined data Name Extension Purpose Description fleet .csv Truck Fleet Dataset with 3 columns and xrows, representing a fleet of x trucks. Examaple: Table 9 config .yml Configuration Parameters YAML file with configuration variables that are defined by the user and are volatile over time. See Figure 11 Table 7: Relocations example Hour Area Relocation 2017-11-26 12:00:00 177 10 2017-11-26 12:00:00 107 8 2017-11-26 12:00:00 192 8 2017-11-26 12:00:00 9 6 2017-11-26 12:00:00 108 6 2017-11-26 12:00:00 162 6 2017-11-26 12:00:00 176 6 2017-11-26 12:00:00 84 -30 2017-11-26 12:00:00 57 -15 2017-11-26 12:00:00 148 -5 Table 8: Distances example X1X2X3X4 Y10332.8 881.3 730.6 Y2332.80776.1 398.3 Y3881.3 776.10851.8 Y4730.6 398.3 851.80 Table 9: Fleet example Plate Capacity available 11 −XX −22 15 TRUE 22 −YY −33 15 TRUE 33 −ZZ −44 10 FALSE
4.2. Read Data 35 --- config . yml journey: limit:60 #time , in minutes , to rebalance the system velocity:750 #m/min - 45km/h average speed during a trip depot:84 #depot operations: bycicles: pickup:1#average time spent on picking up a bycicle deliver:1#average time spent on delivering a bycicle scooters: pickup:1#average time spent on picking up a scooter deliver:1#average time spent on delivering a scooter --- Figure 11: YAML configuration file To relate to the example with the formulation of the problem present in Section 3.1, Figure 12 tends to clarify the reader about the construction of the graph, corresponding to each problem instance (fictitious values). Hour Area Relocation 2017-11-26 12:00:00 177 10 2017-11-26 12:00:00 107 8 2017-11-26 12:00:00 192 8 2017-11-26 12:00:00 9 6 di,j Distance di,j Distance d177,107 2 988 d107,192 7 990 d177,192 680 d107,9 9 219 d177,9 10 000 d192,9 5 500 177 107 192 9 10 000 19 219 0 2 988 680 0 7 990 0 5 500 0 Figure 12: Example of a complete directed graph G=(V,A) corresponding to a fictitious instance of the problem
4.2. Read Data 36 Some adaptations were implemented to facilitate the algorithm to always consider feasible solutions. For example, as depicted in Table 7, the stations do not follow an incremental approach (Figure 13), making it arduous to impress a search logic to them. The problem was adressed by maping each station to an identifier (Figure 14), folowing an incremental approach, allowing the algorithm(s) to easilly evaluate the solution and making the boundaries much more ristrict (see Section 4.3.2). In the execution of the optimization module, the algorithm(s) is going to run based on a data frame with the auto increment identifier of each station, the actual need to be addressed and the need after the journey returned by the search (see Table 14). 177 107 192 9 10 000 19 219 0 2 988 680 0 7 990 0 5 500 0 Figure 13: Complete directed graph G = (V, A)fw with real data 1 2 3 4 10 000 19 219 0 2 988 680 0 7 990 0 5 500 0 Figure 14: Complete Directed Graph G = (V, A) fwto feed the system
4.3. Define Search Space and Solution Representation 37 4.3 define search space and solution representation With all global variables defined, all the requirements to represent the solution and the search space are satisfied. Both the search space and the representation of the solution are dynamically derived by the specifications of each instance of the problem. This use case has three distinct redistribution hours each day. Each one of them differs in complexity and demand, requiring different constraints that require consideration. The need to perform each task with high adaptability is crucial and, on account of all the constraints, the solution can be highly variant. It should be noted that the Bike Sharing Problem is a non trivial variant of of the well known Traveling Sales Problem, thus it does not assume just the distance between stations. In effect, the best solution is not the shortest path between stations, but the shortest path that allows a fleet of trucks to fully restore the service level of each station. With this in mind the solution should not only represent the stations, but also the vehicles delivered/picked on each one of them. The most direct way of representing this task is to consider, for each station, the pair station →quantity, in which the station would be its identifier (∈N+) and the quantity to be delivered (∈N+ 0) or picked ( ∈N− 0). This approach would have a straightforward implementation but the search space associated with it could be smaller. Consider that the truck drives to station number 3. This station has a demand for 8 vehicles. So the solution should be 3→-8. So, considering that the truck can carry 15 vehicles simultaneously (Q= 15), the algorithm should consider from 3→-15, to 3→15. This is not an unacceptable search space but it could be more advantageous. Instead of considering the pair station → quantity, we are going to consider the pair station →load, in which the station would be its identifier (∈N+) and load, the truckload leaving the station (∈N+ 0). As the vehicles that can be picked or delivered are constrained by the truck capacity Q, the search space can be optimized, only considering, in this example, 3→0, to 3→15, allowing the algorithm, with the same computational power, to explore regions that can be more meaningful. It should be noted that many Modern Optimization methods are implemented by assuming solutions with a numeric vector. Thus, we assume this representation of solutions, putting each trip in a loop, that will only stop when all service level requirements are quenched or the time window constraint is corrupted. The solution representation is depicted below (Figure 15): solt:S1L1S2L2S3L3[...]Sn−1Ln−1SnLn Pair1Pair2Pair3Pairn−1Pairn Figure 15: Theoretical solution sepresentation where each pair corresponds to the station identifier and the truck load when leaving it.
4.3. Define Search Space and Solution Representation 38 As the solution is driven by constraints, in order to deliver a valid and meaningful solution, its construction should reflect them. As one of the constraints is that each truck operates a course that starts and finishes at the depot, S1should always be considered as the depot and should not be part of the solution representation on the optimization tasks, being the first pair a false one, making the first value of the solution the truck load leaving the depot. solt:S1L1S2L2S3L3[...]Sn−1Ln−1SnLn Depot Pair1Pair2Pairn−1Pairn Figure 16: Practical solution representation To better understand what the solution represents, the following flow tries to facilitate its interpretation. Depot l066V1 l1 '' ooV2l266V[...] l[...] ))Vn−1ln−166Vn 4.3.1Dimension This is a problem that can either be solved by a single trip, carried by a single truck, or by ttrips, performed by mvehicles. We have to consider this factor when we think about the dimension of the solution. To make sure that the system can find a solution for every instance of the problem, its representation and search space should consider that one trip can restore the equilibrium of the system. Consequently, the dimension should be considered as being Vnumber of vertices, multiplied by two (truckload for each one of them), less one (excluding depot). D= (V×2)−1, V∈N+\{1}(2) By the example given in the previous chapter (Section 3.1), we have 10 areas to visit, including depot. So, 10 ×2−1=19.
4.3. Define Search Space and Solution Representation 39 4.3.2Bounds The search space is not only composed by the dimension, but also by the bounds of the solution. These intend to control the dispersion of the generated solutions, maintaining the coherence of the solutions generated with the case study expectations. So, as seen in Figure 16, odd numbers represent the load of the truck when leaving each station, and the even ones, the station identifier. So, following the logic of the autoincrement identifier, for each station and capacity Q, the bounds could be granted by: lower = 0, if iis odd min(N), if iis even i, representing the index of the solution vector upper = Q, if iis odd max(N), if iis even i, representing the index of the solution vector Consider the example given in the previous chapter (Section 3.1): lower :0101010101010101010 upper : 15 10 15 10 15 10 15 10 15 10 15 10 15 10 15 10 15 10 15 Attending to the problem constraints, we ought to consider that the truck must return vacant to the depot. To do so, the last station visited should have a positive demand (delivery node). To meet this business logic in mind, we have to add conditions to our bounds. lower = 0, if iis odd min(N), if iis even, i<{n×2} min(N+), if iis even, i≥ {n×2} i, representing the index of the solution vector upper = Q, if iis odd, i<{n×2} max(N), if iis even, i<{n×2} 0, if iis odd, i≥ {n×2} max(N+), if iis even, i≥ {n×2} i, representing the index of the solution vector which translates into: lower :0101010101010101010 upper : 15 10 15 10 15 10 15 10 15 10 15 10 15 10 15 10 15 7 0
4.4. Search for (sub)Optimal Solution 40 4.4 search for (sub)optimal solution Modern Optimization, also known as metaheuristics, are exceptional when it comes to finding a ’good enough’ solution when there is no simple way to find the absolute best. Two different metaheuristic approaches were considered when modeling this problem; local and population-based search. In the first one, Hill Climbing and Simulated Annealing were implemented, and in the second, Evolutionary Algorithms were considered. The two approaches will be compared throughout this section, giving a thorough explanation of each step of the development, opposing one approach to another and comparing the results at the end. 4.4.1Objective Goal Formulation The evaluation function, also known as fitness, translates the project desired goal; the minimization of the distance traveled in a redistribution instance. minimize Xd(x) where d(x) = n ∑ i=1 i6=n d(i,i+1)i,n∈N+(3) But, if we only consider the distance, this project would not care if the business goals were met or not, making this project just the study and development of a solution to the Traveling Salesman Problem. The goal of the solution is the minimization of the total distance traveled, that can meet the service level requirements of all stations. Since considering the solutions under the single objective of the distance traveled would lead to unacceptable outcomes, this factor should be incorporated in the evaluation formula. minimize Xd(x) + αr(x) where d(x) = n ∑ i=1 i6=n d(i,i+1)i,n∈N+ r(x) = n ∑ i=1 r(|i|)i,n∈N+ (4) In some cases, solutions can be improved by incorporating some domain knowledge. As this is an incremental approach, the redistribution can be performed by ttrips. To align with business goals and to enhance the algorithm performance, each trip should also maximize the demand. For instance, supplied stations should no longer be considered in
4.4. Search for (sub)Optimal Solution 47 Example (continuation) This technique allows the return to stations already visited on the same trip. This addresses a purpose that can be crucial to making the most of the available time. So we can look at the third technique as an improved version of the second, giving the solution generation more flexibility. With the repetition of stations, we could exchange one that could not be updated with any that could. For example, just by switching from 6 to 9, and recalculating the loads, we could build an even more relevant initial solution. Table 12 represents the impact that this small change would have on the system service level requirements. s:15594391579101426306010 s:15594391579101426309310 stations_visited : 5 4 9 7 10 2 3 9 1 truck_load : 15 9 3 15 9 14 6 0 3 0 Figure 26: Output example of the third solution generation technique Table 12: System new state Station Demand Need After 1 10 7 2 8 0 3 8 2 4 6 0 5 6 0 6 6 6 7 6 0 8-30 -15 9-15 0 10 -5 0 With this minor change, it was possible to prepare an initial solution that satisfies the service requirements from 60% of the stations. These techniques are undoubtedly an asset to the final solution. Practical results of the implementation of these techniques detailed in Section 5.1.2
4.4. Search for (sub)Optimal Solution 48 4.4.3Change and Breeding (Genetic Operators) To consider solutions in the neighborhood of the one(s) in memory, some adjustments must be made to the current ones, in order to discover and exploit some more interesting areas of the search space. These adjustments differ for each instance, some being more challenging than others. The system logic and the solution representation will dictate these adjustments. The problem that we have in hands is a ’hybrid integer’. Integer because all elements are treated as integers; Hybrid because of its nature, composed by elements that hold a different meaning, being addressed differently. On one hand, with the stations we are in the presence of a combinatorial problem and, on the other hand, with the load of the trucks, we have a (discrete) numerical problem. Thus, we have to be very careful when addressing this problem, applying different techniques in the same change. 4.4.3.1Change When working with a single solution, the adjustments made in the solution to exploit its neighborhood are denominated ’change’. In this hybrid problem we, first need to divide the solution in stations visited and truck load, as in Figure 18. As we can split this problem in two, it makes sense to have at least three change options: • only stations are modified; • only the truck load is changed; and • both stations and truck load are modified.
4.4. Search for (sub)Optimal Solution 49 Combinatorial Problem In this problem, the objective is to find combination of stations that optimizes the score of the evaluation function (see Section 4.4.1). Since the main goal is the visit all stations by the shortest path, this problem can be solved by considering the permutation of the stations {1, 2, 3, ..., n}. A permutation describes an arrangement or ordering of items. There are n! permutations of nitems. This grows so exponentially that the amount of time to generate all permutations would be gigantic, for n>12, since 12! = 479, 001, 600 (Skiena,2010). With (meta)heuristics we can set a maximum number of iterations to assure that the algorithm does not take too long to generate a satisfying solution. The vector that stores the sequence of stations to be visited can be reordered, through the permutation of the elements. This is a typical combinatorial problem. From (Cortez,2014) we can see examples of mutation operators for the Traveling Salesman Problem. They were considered and implemented but were forced to satisfy the problem constraints. These examples are depicted in Figure 27: exchange, insertion, and displacement. The first operator swaps two randomly selected cities, the following inserts a city into an arbitrary position and the third inserts a random subtour into another position. Figure 27: Example of three mutation operators, adapted from (Cortez,2014) However, this is not a pure Traveling Salesman Problem. For instance, the repetition of a station may improve the quality of the solution. This was previously discussed in Section 4.4.2.2, but here we examine how it works. Instead of just permutate the stations’ vector, the injection operator stores in memory the stations to visit; selects a random element and, instead of swapping it with another from the same vector, it removes it from the solution and adds another element from the vector in memory. Figure 28: Injection operator
4.4. Search for (sub)Optimal Solution 50 There is also a key factor in this operator. If the user decides so (through defining a Boolean variable as TRUE), it can allow the operator to accept one station to appear followed by the same one, shortening the trip - through a logic repair, Algorithm 8. Using some domain knowledge with some trial and error we can also associate with each type of change, a probability of occurring. The probability of exchange and insertion operators has an associated probability of 0.3 each, while displacement has a probability of 0.2. We just want a trip to be introduced from afar; therefore, the probability associated with the injection operator is 0.1. Sometimes we also want no changes in the stations, but only in the associated load, thus leaving 0.1 probability to no modifications.
4.4. Search for (sub)Optimal Solution 51 Examples Starting from the solution represented in Figure 29, the operators will be exemplified. V1l199V2 l2 %% ooV3l399 V4 l4 %%V5l599 V6 l6 %%V7l799 V8 l8 %%V9l988 V10 Figure 29: Practical representation of a solution Exchange V1l199V2 l2 %% ooV6l699 V4 l4 %%V5l599 V3 l3 %%V7l799 V8 l8 %%V9l988 V10 Figure 30: Practical representation of exchange operator Insertion V1l199V2 l2 %% ooV3l399 V4 l4 %%V9l999 V5 l5 %%V6l699V7 l7 %%V8l888 V10 Figure 31: Practical representation of insertion operator Displacement V1l199V2 l2 %% ooV7l799 V8 l8 %%V9l999 V3 l3 %%V4l499 V5 l5 %%V6l688 V10 Figure 32: Practical representation of displacement operator Injection V1l199V2 l2 %% ooV3l399 V4 l4 %%V5l599 V6 l6 %%V7l799 V8 l8 %%V9 l9 ee Figure 33: Practical representation of injection operator
4.4. Search for (sub)Optimal Solution 52 Numerical Problem The Bike Sharing Rebalancing Problem is different from the Traveling Salesman Problem because it has the mission of rebalancing a sharing system. This increases the problem difficulty but has a tremendous potential to be adapted to a mundane problem, being able to make life easier for many. To work with the loads, we needed an operator that would allow us to make small changes in values, trying to come up with new ones that would allow us to get an interesting trade-off for future solutions. Thus originated the differential operator, which chooses vvalues from [1, n],v∈N+, and adds xfrom [−1, 1],x∈N+. That is, choose a set of indexes from the vector and add or remove the values 0 or 1. Examples of this operator are shown in Figures 34 and 35. Figure 34: Differential operator Example V1l199V2 l2 %% ooV3 l3−1 99 V4 l4 %%V5l599 V6 l6+1 %%V7l799 V8 l8 %%V9 l9+0 88 V10 Figure 35: Practical representation of differential operator
4.4. Search for (sub)Optimal Solution 53 4.4.3.2Breeding (Genetic Operators) In the presence of a population, rather than a single solution, the possibilities of generating new solutions increase, being able, in addition to changing the solution individually, to cross with others, taking advantage of their diversity to explore regions of the search space that otherwise it would not be possible. So, in addition to the mutation operators we just discussed, we added a crossover technique. The crossover operator is a genetic operator that combines two solutions (parents) to produce a new one (children). The ideia behind crossover is that the children might be better than both parents, if he takes the best characteristics from each parent. One of the most basic operators to understand and implement has been adopted in the system development. Despite its simplicity, it fits properly in this particular problem. The operator is the single point (or one point) crossover, where both parents are split at a randomly determined crossover point. Then, a new child is created by appending the first part of the first parent with the the second part of the second (Altenberg,1995). Figure 36 depicts the single point crossover process and Karlin and Liberman (1978) describes it by: R(r) = 1/(L−1)if L−1 ∑ i=1 |ri+1−ri|=1, 0, otherwise Both crossover and mutation operators occur during the evolution, according to an a priori defined probability. The probability applied to the crossover is 0.4, and the probability of a mutation is 0.6. Each mutation operator has its own associated probability (see Section 4.4.3.1). Figure 36: Single-point crossover
4.5. Repair 54 4.5 repair The goal of this section is not to give an exact blueprint of the way that the functions perform, but to elucidate the reader about the inherent logic. For each optimized trip that the algorithm returns, there is a repair at the station level, ensuring that it does not make unnecessary trips. The algorithm can visit a station and do nothing (does not leave or lift vehicles). When this occurs, the repair procedure removes such unnecessary trip, therefore optimizing the travel time to the maximum. s: 15 5 10 5 8 4 10 8 2 3 2 9 0 s: 15 5 10 5 8 4 10 8 2 9 0 Attached to this, as the same station can appear more than once in the solution, there is the possibility that they will appear one after the other, meaning that a trip will link to the same geographical point. When this happens, the procedure detects the occurrence, eliminating the redundancy. With the logic of the solution representation, dictating the obliviation of the first station and load. s: 15 5 10 5 8 4 10 8 2 15 7 9 0 s: 15 5 8 4 10 8 2 15 7 9 0 Algorithm 8demonstrates in detail the execution of the logical repair of the solution. Algorithm 8Solution repair method Input: s(solution) truck_load ←odd(s).Truck load throughout the journey stations_visited ←even(s).Stations visited throughout the journey waste ←[] .Empty Array to store useless trips for load in truck_load do .Go through the array if load =next_load then .See if loads are equal waste ←append(load_position).Save position in the solution array waste ←append(station_position).Save also the station position end if end for s←remove(s,waste).Remove useless trips from the solution waste ←[] .Empty Array to store repeated stations for station in stations_visited do .Go through the array if station =next_station then .See if stations are equal waste ←append(station_position).Save position in the solution array waste ←append(load_position).Save also the load position end if end for s←remove(s,waste).Remove useless trips from the solution Output: s
4.5. Repair 55 After this, there is also a repair at the vehicle load level. The algorithm determines that a truck, on a journey, can only carry a certain number of vehicles, but in some situations, it may carry more than indicated. This adjustment deals with those situations, making the system more reliable. s: 15 5 10 5 8 4 10 8 2 3 2 9 0 s: 15 5 10 5 8 4 12 8 4 3 2 9 0 Algorithm 9demonstrates in detail the execution of the logical repair of the solution. Algorithm 9Load repair Input: s(solution), t(truck), l(service levels) truck_capacity ←capacity(t).Truck load throughout the journey situation ←demand(l,s).Number of vehicles left to redistribute imp ←improvement(t,l,s).Load improvement for each station until Q indexes ←(imp,l,s).Indexes that can be improved for iin indexes do .Go through the array s←re f orm(indexes,imp,s).Change indexes load end for Output: s More than logical corrections to the solution, the implemented repairs attempt to address the weaknesses that the randomness of metaheuristics bring, enriching the system with domain knowledge. While Algorithm 8only compares the stations and loads with those immediately followed in the solution, the Algorithm 9tries to figure out where to add/remove load throughout the solution, i.e., without fiddling with the sequence of stations that the search output delivered, tries to find a possible solution that the system may not have been able to acknowledge.
4.6. Save Results 56 4.6 save results As we saw in Section 4.1, the final solution should deliver the final journey collection distributed by the fleet available at the time of redistribution. Its structure is theoretically represented by: sol = l11 l12 . . . l1n l21 l22 . . . l2n . . .. . ..... . . lt1lt2. . . ltn Where, trepresents each trip, nthe station visited and lthe load that the truck has when leaving each station n. For system understanding, ease of implementation and readability, the results are stored as a matrix, composed by the vectors of the solutions generated in the loop. Table 13: System output with final journeys t s0ls0s1ls1s2ls2s3ls3· · · sn−1lsn−1snlsn 1 8 15 1 5 10 10 5 8 · · · 3 2 6 0 2 8 12 5 2 3 0 10 5 · · · 6 0 × × . . .. . .. . .. . .. . .. . .. . .. . .. . .· · · . . .. . .. . .. . . t8 0 7 4 10 0 × × · · · × × × × Where s0represents the depot indicator, ls0the truck load leaving the base, and so on, representing, in order, the stations to visit and the load, leaving each one of them.
5.1. Solution Generation Approaches and Weight Experimentation 63 Figure 38: Length for different weight scenarios Figure 39: Duration for different weight scenarios Figure 40: Execution time for different weight scenarios
5.1. Solution Generation Approaches and Weight Experimentation 64 5.1.2Initial Solution/Population Experimentation Local Based Approach Experimentation Two algorithms were implemented from those mentioned and explained in Section 2.3.2: Simulated Annealing and Hill Climbing. With the same principles but with different behavior, we are going to examine which one best fits the issue at hand. First, we try to understand the impact that the custom generation of initial solutions have in the search for solutions. These results are compared with the previously obtained results, described in the Table 19. These values were obtained following the methodology for custom solution generation promoted by this research work (see Section 4.4.2.1). When the initial solution generation is random, the search begins at a random starting point within the search space. That position can be good or bad. By not using domain knowledge, we are using a completely random initial search position. However, the search task could benefit from the utilization of a much more attractive initial point by assuming domain knowledge. Table 20: Optimization results for the single-state algorithms using random and customized generation of initial solutions (best values in bold) Random Generation Length Duration Execution Hill Climbing 29373, 54 21.34 25.56 Simulated Annealing 28914.40 20.45 24.21 Custom Generation Hill Climbing 21712.66 16.87 17.89 Simulated Annealing 21521.51 16.53 18.28 Table 20 confirms the gain of using the methodology presented in this document, being advantageous in all the assessment metrics considered: the length (m), the duration (min) of the journey, and the execution time of the search task (sec).
5.1. Solution Generation Approaches and Weight Experimentation 65 Population Based Approach Experimentation Above we look at the benefits of generating a single initial solution, but when the search algorithm considers an initial population, does the benefit remain? As described in Section 2.3.2.2, population-based algorithms, such as the Evolutionary Algorithms implemented in this paper, consider several solutions as a starting point. The importance of setting the initial population in meaningful places of the search space can become even more fundamental than in single-state approaches. The utilization of various initial points in the search space allows to explore diverse interesting and relevant areas of the problem and not to restrict to a specific area. Hence, as we also saw in Section 4.4.2.2, the strategy adopted for early population generation is to consider multiple domain knowledge applications to explore most of the search space, in order to find a solution flexible enough to adapt to different instances of the problem. Table 21: Optimization results for the population-based algorithms using random and customized generation of the initial population (best values in bold) Random Generation Length Duration Execution Evolutionary Algorithms 28644.75 22.463 24.15 Custom Generation Evolutionary Algorithms 21605.63 16.49 16.43 Table 21 presents the results obtained when considering the strategy adopted in this paper (see Section 4.4.2.2) and also results not using domain knowledge, confirming that for this problem, the randomness in solution generation is outweighed by the benefits of biased solutions. These results confirm that the customized method for generating initial solutions results in enhanced optimizations for both single-state and population-based methods.
5.2. System Experimentation 66 5.2 system experimentation This section presents the experiments executed for different scenarios to verify the versatility and flexibility of the system to meet the many challenges of the real sharing service. A major business concern is the conformity with a time window. Therefore, system rules had to be considered to make the most of the available time because time may not be enough to reestablish service levels. Thus, the system follows two principles: • the initial load for each truck must be packed when the rebalancing begins and • for each truck’s last trip, the travel time back to the depot is not accounted for. In this study only two scenarios will be presented here for analysis purposes. For reasons of compliance and understanding, the instance that underpins the scenarios is the one previously described in Section 3.1.1.Scenario I is the same as the one used by the author for the solution proposed in Figure 9, where two trucks with capacity for 15 vehicles are considered (Q=15). For scenario II, only one truck is considered, also with capacity for 15 vehicles (Q=15). The results of the experiment are represented in Table 22, with each value being the result of the average from 10 observations. Each scenario environment can be revisited in A. The time considered for redistribution, agreed with Nuno Oliveira, was 1 hour (60 min), with the operational loading/unloading time of 1 min for each vehicle. Table 22: Optimization results for system trial (best values (for each scenario) in bold) Scenario I Length Duration Missed Stations Execution Hill Climbing 21737.86 58.14 0 0 31.51 Simulated Annealing 22389.75 57.27 0 0 51.63 Evolutionary Algorithms 22033.04 58.75 0 0 49.46 Scenario II Hill Climbing 11373.31 58.42 22.1 5.9 36.09 Simulated Annealing 11987.03 57.19 20.2 5.8 59.56 Evolutionary Algorithms 12085.54 58.57 20 5.4 36.91
5.2. System Experimentation 67 Table 22 shows that the utilization of only one truck to redistribute, conditions the main business goal of meeting the service level requirements. In general, the search algorithm is able to find a solution that enables effective system rebalancing. However, the organizational infrastructure has to be aligned with the requirements of the problem. When the service level requirements have been met, the metrics considered and analyzed to choose the best solution and/or algorithm are the distance traveled and the duration of the redistribution, taking into account the operational time. According to Nuno Oliveira, the execution of the redistribution in the shortest possible time and distance is a big competitive advantage because it reduces costs of relocation (e.g., fuel, staff, maintenance vehicles) and monetize resources (e.g., vehicles are available sooner). Based on the same logic, we can understand that when it is not possible to meet the requirements, the most important metrics should be the vehicles that have not been redistributed and the stations that have remained in need. In scenario I, although the Hill Climbing algorithm has the best result in terms of distance traveled during redistribution, Simulated Annealing has a notable advantage in averaging redistribution duration. All of them satisfy the requirements, but 1 minute can be the difference between losing a customer or not. In scenario II, the results tend to give an advantage to Evolutionary Algorithms. This scenario is undoubtedly more demanding in terms of deliverables and is perhaps a more realistic scenario in terms that the conditions for full redistribution cannot always be met. Although it takes longer, and travel further, the solutions proposed by the Evolutionary Algorithms can, on average, satisfy more stations than other algorithms. We realize that to always ensure that the best possible solution is found, we must guarantee that multiple searches are generated, various algorithms are tested and that the viability of the final output is considered. The user should be able to decide which one is the best according to their needs. The display of diverse metrics is valuable to support the user in their decision.
5.3. Discussion 68 5.3 discussion 5.3.1Author Defined Solution To further analyze the system, we will try to contrast the system solutions with the solution defined by the author of this thesis, represented in Figure 9. It is important to realize that the handmade solution took a long time, demonstrating the importance of this type of system. A more complete assessment of the utility of this system can be done by comparing with the author’s solution. Table 23 demonstrates the solution of Figure 9in the system deliverable scheme. Table 23: Author defined solution v t ls0s1ls1s2ls2s3ls3s4ls4s5ls5s6ls6s7ls7 1 1 15 3 7 6 1 4 0 9 15 4 10 7 4 2 0 2 2 15 5 9 10 14 2 10 1 0 × × × × × × cjPlate Length Duration Trip Missed Stations c1XYZ 12856.56 58.81 1 0 0 ckZYX 9375.44 33.36 1 0 f w0f w Total −22232 58.81 −0 0 The first trip has considerable size and its duration is very close to the 60min limit. We are going to consider it to understand how the duration metric is evaluated. The second trip takes less time because it is shorter, with fewer vehicles to redistribute. This one will not be analyzed in detail. The first trip (t1) is represented by: s:153761409154107420 stations_visited : 3 6 4 9 4 7 2 truck_load : 15 7 1 0 15 10 4 0
5.3. Discussion 69 Figure 41 shows the calculation of the operational time for the first trip (t1), considering 1min for vehicle loading/unloading. As explained earlier, we consider that the first loading of each truck do not count as operational time. truck_load : 15 7 1 0 15 10 4 0 8min 6min 1min 15min 5min 6min 4min Figure 41: Operational time from t1 Thus, the operational time is given by the sum of the difference between nand n+1 values. Therefore: operational_time = (15 −7) + (7−1) + (1−0) + |(0−15)|+ (15 −10) + (10 −4) + (4−0) operational_time = (8) + (6) + (1) + (15) + (5) + (6) + (4) operational_time =45 As we can see from the operational time required for only one route, the travel time must be reduced to enable a redistribution that respects the time window stipulated by the user. Considering the time window of 60 minutes, there are only 15 minutes left to spend driving between stations. Considering an average speed of 45km/h(750m/min) along the entire route, we can translate a maximum distance that the trip must meet. max_distance =remain_time ×average_speed max_distance =15 ×750 max_distance =11250
5.3. Discussion 70 Looking at the Table 23 we notice that, even though it is close, the distance traveled during redistribution (12856.56 m) exceeds 11250 of the remaining time. The elapsed travel time is then: travel_time =trip_length average_speed travel_time =12856.56 750 travel_time =17.14 Knowing that the duration will exceed the expected, the total time (duration) is given by: total_time =operational_time +travel_time total_time =45 ×17.14 total_time =62.5 As already mentioned, the return trip from the last journey of each truck does not count to the redistribution time (a measure adopted to optimize the algorithm performance and increase the chances of finding better solutions). So, the distance between the last station and the depot does not add to the journey duration, only for the distance traveled. Therefore, we have to exclude the distance between 2 (last station) and 8 (identifier of the depot). return_trip =trip_length(ind,depot) average_speed duration =total_time −return_trip duration =62.5 −2770.373 750 duration =62.5 −3.69 duratioin =58.81 With the thoroughness of the problem, it becomes a very difficult task for a human to perform quickly and effectively. All possible combinations make each instance a complex challenge.
5.3. Discussion 71 5.3.2System Solution The processing speed of a computer is always higher than human work particularly for small, specific and repetitive tasks. Therefore, a system that performs these sorts of tasks is always a valuable asset for the organization and the general welfare. Table 24 presents a solution generated by Evolutionary Algorithms, where the deliverable provides a feasible and better solution than the presented by the author of the thesis, shown in Table 23. This solution visits one less station on the first trip, managing to make a tradeoff with the second truck, improving the overall response time. Table 24: System solution v t ls0s1ls1s2ls2s3ls3s4ls4s5ls5s6ls6 1 1 15 6 9 1 0 9 15 4 9 1 8 3 0 2 2 15 7 9 2 1 10 6 5 0 × × × × cjPlate Length Duration Trip Missed Stations c1XYZ 11074.32 56.16 1 0 0 ckZYX 9507.44 34.54 1 0 f w0f w Total −20581.76 56.16 −0 0 In less than a minute, the metaheuristics were able to test thousands of different combinations, saving time, stress and resources to the organization. Figures 42 and 43 represent the routes that redistribute the service. Comparing the images, we can see that the system output (Figure 42) trips are ’cleaner’ and more direct than those of the author’s solution (Figure 43). This again demonstrates the significance of implementing such solutions, confirming their value to organizations.
5.3. Discussion 72 Figure 42: System solution representation on Barcelona map
Bibliography 79 Research,240(3):718–733, February 2015. doi: 10.1016/j.ejor.2014.07.020. URL https: //doi.org/10.1016/j.ejor.2014.07.020. Brinkmann, J., Ulmer, M. W., and Mattfeld, D. C. Inventory routing for bike sharing systems. Transportation Research Procedia,19:316–327,2016. doi: 10.1016/j.trpro.2016.12.091. URL https://doi.org/10.1016/j.trpro.2016.12.091. Bude, p. Global smart infrastructure—smart city transformation 2016.2016. Caggiani, L. and Ottomanelli, M. A modular soft computing based method for vehicles repositioning in bike-sharing systems. Procedia - Social and Behavioral Sciences,54:675– 684, October 2012. doi: 10.1016/j.sbspro.2012.09.785. URL https://doi.org/10.1016/j. sbspro.2012.09.785. Caggiani, L. and Ottomanelli, M. A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems. Procedia - Social and Behavioral Sciences,87:203– 210, October 2013. doi: 10.1016/j.sbspro.2013.10.604. URL https://doi.org/10.1016/j. sbspro.2013.10.604. Chemla, D., Meunier, F., and Calvo, R. W. Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization,10(2):120–146, May 2013. doi: 10.1016/j.disopt.2012. 11.005. URL https://doi.org/10.1016/j.disopt.2012.11.005. Chiariotti, F., Pielli, C., Zanella, A., and Zorzi, M. A dynamic approach to rebalancing bike-sharing systems. Sensors,18(2):512, February 2018. doi: 10.3390/s18020512. URL https://doi.org/10.3390/s18020512. Chow, J. Y. and Sayarshad, H. R. Symbiotic network design strategies in the presence of coexisting transportation networks. Transportation Research Part B: Methodological,62:13– 34, April 2014. doi: 10.1016/j.trb.2014.01.008. URL https://doi.org/10.1016/j.trb. 2014.01.008. Contardo, C., Morency, C., Rousseau, L., and Centre interuniversitaire de recherche sur les réseaux d’entreprise, l. l. e. l. t. Balancing a Dynamic Public Bike-sharing System. CIRRELT (Collection). CIRRELT, 2012. URL https://books.google.pt/books?id= QEZBDQEACAAJ. Correia, G. and Antunes, A. P. Optimization approach to depot location and trip selection in one-way carsharing systems. Transportation Research Part E: Logistics and Transportation Review,48(1):233–247, January 2012. doi: 10.1016/j.tre.2011.06.003. URL https://doi. org/10.1016/j.tre.2011.06.003. Cortez, P. Modern Optimization with R. Springer International Publishing, 2014. doi: 10. 1007/978-3-319-08263-9. URL https://doi.org/10.1007/978-3-319-08263-9.
Bibliography 80 Dell'Amico, M., Hadjicostantinou, E., Iori, M., and Novellani, S. The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega,45:7–19, June 2014. doi: 10.1016/j.omega.2013.12.001. URL https://doi.org/10.1016/j.omega.2013. 12.001. Docherty, I. New governance challenges in the era of ‘smart’ mobility. In Governance of the Smart Mobility Transition, pages 19–32. Emerald Publishing Limited, March 2018. doi: 10.1108/978-1-78754-317-120181002. URL https://doi.org/10.1108/ 978-1-78754-317-120181002. Dror, M., Fortin, D., and Roucairol, C. Redistribution of Self-service Electric Cars: A Case of Pickup and Delivery. Research Report RR-3543, INRIA, 1998. URL https://hal.inria. fr/inria-00073142. Projet PRAXITELE. Fan, W. D., Machemehl, R. B., and Lownes, N. E. Carsharing. Transportation Research Record: Journal of the Transportation Research Board,2063(1):97–104, January 2008. doi: 10.3141/2063-12. URL https://doi.org/10.3141/2063-12. Froehlicj, J., Neumann, J., and Oliver, N. Sensing and pedicting the pulse of the city through shared bicycling. 2008. Gavalas, D., Konstantopoulos, C., and Pantziou, G. Design and management of vehicle-sharing systems: A survey of algorithmic approaches, pages 261–289.12 2016. ISBN 9780128034545. doi: 10.1016/B978-0-12-803454-5.00013-4. Gel’fand, I. M. Lectures on Linear Algebra (Dover Books on Mathematics). Dover Publications, 1989. ISBN 0486660826. URL https://www.amazon.com/ Lectures-Linear-Algebra-Dover-Mathematics/dp/0486660826?SubscriptionId= AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp=2025&creative= 165953&creativeASIN=0486660826. Ghosh, S., Varakantham, P., Adulyasak, Y., and Jaillet, P. Dynamic repositioning to reduce lost demand in bike sharing systems. Journal of Artificial Intelligence Research,58:387–430, February 2017. doi: 10.1613/jair.5308. URL https://doi.org/10.1613/jair.5308. Gong, Y.-J., Zhang, J., Liu, O., Huang, R.-Z., Chung, H. S.-H., and Shi, Y.-H. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews),42(2):254–267, March 2012. doi: 10.1109/tsmcc.2011.2148712. URL https://doi. org/10.1109/tsmcc.2011.2148712. Goodall, W., Tiffany Dovey, F., Bornstein, J., and Bonthron, B. The rise of mobility as a service. 2017.
Bibliography 81 Hemdersom, J. and Fishman, A. Divvy: Helping chicago’s new bike share find its balance. Data Science for Social Good,2013. Hietanen, S. Mobility as a service - the new transport model? 2014. Hillier, F. S. and Liberman, G. J. Introduction to Operations Research. McGraw-Hill, 2014. ISBN 0073523453. URL https://www.amazon.com/ Introduction-Operations-Research-Frederick-Hillier/dp/0073523453? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=0073523453. ITF-CPB. Transition to shared mobility: How large cities can deliver inclusive transport services. page 54, May 2017. Karlin, S. and Liberman, U. Classifications and comparisons of multilocus recombination distributions. Proceedings of the National Academy of Sciences of the United States of America, 75(12):6332–6336,1978. ISSN 00278424. URL http://www.jstor.org/stable/68958. Keen, P. G. W. and Scott-Morton, M. S. Decision Support Systems: An Organizational Perspective (Addison-Wesley series on decision support). AddisonWesley, 1978. ISBN 0201036673. URL https://www.amazon.com/ Decision-Support-Systems-Organizational-Addison-Wesley/dp/0201036673? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=0201036673. Kek, A. G., Cheu, R. L., Meng, Q., and Fung, C. H. A decision support system for vehicle relocation operations in carsharing systems. Transportation Research Part E: Logistics and Transportation Review,45(1):149–158, January 2009. doi: 10.1016/j.tre.2008.02.008. URL https://doi.org/10.1016/j.tre.2008.02.008. Kleinberg, J. and Tardos, E. Algorithm Design. Pearson, 2006. ISBN 9780321295354. URL https://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=0321295358. Lei, H., Laporte, G., and Guo, B. The vehicle routing problem with stochastic demands and split deliveries. INFOR: Information Systems and Operational Research,50(2):59–71, May 2012. doi: 10.3138/infor.50.2.059. URL https://doi.org/10.3138/infor.50.2.059. Lin, J.-R. and Yang, T.-H. Strategic design of public bicycle sharing systems with service level constraints. Transportation Research Part E: Logistics and Transportation Review,47(2): 284–294, March 2011. doi: 10.1016/j.tre.2010.09.004. URL https://doi.org/10.1016/j. tre.2010.09.004.
Bibliography 82 Lin, S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal,44(10):2245–2269, Dec 1965. doi: 10.1002/j.1538-7305.1965.tb04146.x. Luenberger, D. G. and Ye, Y. Linear and Nonlinear Programming. Springer US, 2008. doi: 10.1007/978-0-387-74503-9. URL https://doi.org/10.1007/978-0-387-74503-9. Luke, S. Essentials of Metaheuristics (Second Edition). lulu.com, 2013. ISBN 1300549629. URL https://www.amazon.com/Essentials-Metaheuristics-Second-Sean-Luke/dp/ 1300549629?SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode= xm2&camp=2025&creative=165953&creativeASIN=1300549629. Mak, K. and Guo, Z. A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows. In Proceedings of the 2004 IEEE Systems and Information Engineering Design Symposium, 2004.IEEE, 2004. doi: 10.1109/sieds.2004.239880. URL https://doi.org/10.1109/sieds.2004.239880. Marinakis, Y., Marinaki, M., and Dounias, G. A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence,23(4):463–472, June 2010. doi: 10.1016/j.engappai.2010.02.002. URL https: //doi.org/10.1016/j.engappai.2010.02.002. Marinakis, Y., Iordanidou, G.-R., and Marinaki, M. Particle swarm optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing,13(4):1693– 1704, April 2013. doi: 10.1016/j.asoc.2013.01.007. URL https://doi.org/10.1016/j. asoc.2013.01.007. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer, 1996. ISBN 3540606769. URL https://www.amazon. com/Genetic-Algorithms-Structures-Evolution-Programs/dp/3540606769? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=3540606769. Michalewicz, Z. Adaptive Business Intelligence. Springer, 2007. ISBN 3540329285. URL https://www.amazon.com/Adaptive-Business-Intelligence-Zbigniew-Michalewicz/ dp/3540329285?SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20& linkCode=xm2&camp=2025&creative=165953&creativeASIN=3540329285. Michalewicz, Z. and Fogel, D. B. How to Solve It: Modern Heuristics. Springer, 2004. ISBN 3540660615. URL https://www.amazon.com/ How-Solve-Heuristics-Zbigniew-Michalewicz/dp/3540660615?SubscriptionId= AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp=2025&creative= 165953&creativeASIN=3540660615.
Bibliography 83 Michalewicz, Z., Schmidt, M., Michalewicz, M., and Chiriac, C. Adaptive Business Intelligence. Springer, 2006. ISBN 3540329285. URL https://www.amazon. com/Adaptive-Business-Intelligence-Zbigniew-Michalewicz/dp/3540329285? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=3540329285. Mitchell, W. Mobility on demand. 2008. Moura, L. Introduction to the theory of np-completeness. page 66,2006. Mulley, C. Mobility as a services (MaaS) – does it have critical mass? Transport Reviews,37 (3):247–251, March 2017. doi: 10.1080/01441647.2017.1280932. URL https://doi.org/10. 1080/01441647.2017.1280932. Nair, R. and Miller-Hooks, E. Fleet management for vehicle sharing operations. Transportation Science,45(4):524–540, November 2011. doi: 10.1287/trsc.1100.0347. URL https://doi.org/10.1287/trsc.1100.0347. Nourinejad, M. and Roorda, M. Carsharing operations policies: a comparison between oneway and two-way systems. Transportation,42,05 2015. doi: 10.1007/s11116-015-9604-3. Nourinejad, M. and Roorda, M. J. A dynamic carsharing decision support system. Transportation Research Part E: Logistics and Transportation Review,66:36–50, June 2014. doi: 10.1016/j.tre.2014.03.003. URL https://doi.org/10.1016/j.tre.2014.03.003. O’Mahony, D. B., Eoin an Shmoys. Data analysis and optimization for (citi)bike sharing. 2015. Pangbourne, K., Stead, D., Mladenovi´c, M., and Milakis, D. The case of mobility as a service: A critical reflection on challenges for urban transport and mobility governance. In Governance of the Smart Mobility Transition, pages 33–48. Emerald Publishing Limited, March 2018. doi: 10.1108/978-1-78754-317-120181003. URL https://doi.org/10.1108/ 978-1-78754-317-120181003. Rao, S. S. Engineering optimization: theory and practice. John Wiley & Sons, 2009. Raviv, T., Tzur, M., and Forma, I. A. Static repositioning in a bike-sharing system: models and solution approaches. EURO Journal on Transportation and Logistics,2(3):187– 229, January 2013. doi: 10.1007/s13676-012-0017-6. URL https://doi.org/10.1007/ s13676-012-0017-6. Regue, R. and Recker, W. Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing problem. Transportation Research Part E: Logistics and Transportation Review,72:192–209, December 2014. doi: 10.1016/j.tre.2014.10.005. URL https: //doi.org/10.1016/j.tre.2014.10.005.
Bibliography 84 Rizzoli, A. E., Montemanni, R., Lucibello, E., and Gambardella, L. M. Ant colony optimization for real-world vehicle routing problems. Swarm Intelligence,1(2):135–151, September 2007. doi: 10.1007/s11721-007-0005-x. URL https://doi.org/10.1007/ s11721-007-0005-x. Schuijbroek, J., Hampshire, R., and van Hoeve, W.-J. Inventory rebalancing and vehicle routing in bike sharing systems. European Journal of Operational Research,257(3):992– 1004, March 2013. doi: 10.1016/j.ejor.2016.08.029. URL https://doi.org/10.1016/j. ejor.2016.08.029. Schuijbroek, J., Hampshire, R., and van Hoeve, W.-J. Inventory rebalancing and vehicle routing in bike sharing systems. European Journal of Operational Research,257(3):992– 1004, March 2017. doi: 10.1016/j.ejor.2016.08.029. URL https://doi.org/10.1016/j. ejor.2016.08.029. Signorile, P., Larosa, V., and Spiru, A. Mobility as a service: a new model for sustainable mobility in tourism. Worldwide Hospitality and Tourism Themes,10(2):185–200, April 2018. doi: 10.1108/whatt-12-2017-0083. URL https://doi.org/10.1108/whatt-12-2017-0083. Skiena, S. S. S. The Algorithm Design Manual. Springer, 2010. ISBN 1849967202. URL https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202? SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode=xm2&camp= 2025&creative=165953&creativeASIN=1849967202. Turban, E., Sharda, R. E., and Delen, D. Decision Support and Business Intelligence Systems (9th Edition). Prentice Hall, 2010. ISBN 013610729X. URL https://www.amazon.com/Decision-Support-Business-Intelligence-Systems/dp/ 013610729X?SubscriptionId=AKIAIOBINVZYXZQZ2U3A&tag=chimbori05-20&linkCode= xm2&camp=2025&creative=165953&creativeASIN=013610729X. Vaira, G. Genetic algorithm for vehicle routing problem. page 158,2014. Vine, S. L., Lee-Gosselin, M., Sivakumar, A., and Polak, J. A new approach to predict the market and impacts of round-trip and point-to-point carsharing systems: Case study of london. Transportation Research Part D: Transport and Environment,32:218–229, October 2014. doi: 10.1016/j.trd.2014.07.005. URL https://doi.org/10.1016/j.trd.2014.07. 005. Vogel, P., Greiser, T., and Mattfeld, D. C. Understanding bike-sharing systems using data mining: Exploring activity patterns. Procedia - Social and Behavioral Sciences,20:514–523, 2011. doi: 10.1016/j.sbspro.2011.08.058. URL https://doi.org/10.1016/j.sbspro.2011. 08.058.
Bibliography 85 Wang, H., Cheu, R., and Lee, D.-H. Dynamic relocating vehicle resources using a microscopic traffic simulation model for carsharing services. In 2010 Third International Joint Conference on Computational Science and Optimization. IEEE, May 2010. doi: 10.1109/cso.2010.98. URL https://doi.org/10.1109/cso.2010.98. Wockatz, P. and Schartau, P. Im traveller needs and uk capability study: supporting the realisation of intelligent mobility in the uk. In IM traveller needs and UK capability study: supporting the realisation of intelligent mobility in the UK, pages 1–35. October 2015. doi: 10.1108/978-1-78754-317-120181002.
A SYSTEM ENVIRONMENT BY SCENARIO This appendix serves as a reminder, if necessary, of the environment behind the scenarios for system experimentation (Section 5.2). a.1 scenário i a.1.1Evaluation Formula minimize Xd(x) + αr(x)−βf(x) where α=1500 & β=100 d(x) = n ∑ i=1 i6=n d(i,i+1)i,n∈N+ r(x) = n ∑ i=1 r(|i|)i,n∈N+ f(x) = n ∑ i=1 [r(|i|) = 0]i,n∈N+ (7) a.1.2Fleet Table 25: Fleet (available and not available) Plate Capacity available XYZ 15 TRUE ZYX 15 TRUE YXZ 10 FALSE 86
A.1. Scenário I 87 a.1.3Service Level Requirements Table 26: Service level requirements for 2017-11-26 12:00:00 Hour Area Relocation ID 2017-11-26 12:00:00 177 10 1 2017-11-26 12:00:00 107 8 2 2017-11-26 12:00:00 192 8 3 2017-11-26 12:00:00 9 6 4 2017-11-26 12:00:00 108 6 5 2017-11-26 12:00:00 162 6 6 2017-11-26 12:00:00 176 6 7 2017-11-26 12:00:00 84 -30 8 2017-11-26 12:00:00 57 -15 9 2017-11-26 12:00:00 148 -5 10 a.1.4Geospatial Coordinates Table 27: Stations(areas) locations ID Area Latitude Longitude 1 177 41.39446 2.155730 2 107 41.39134 2.146347 3 192 41.39084 2.153818 4 9 41.40213 2.165954 5 108 41.38893 2.149614 6 162 41.39574 2.160796 7 176 41.39682 2.152529 8 84 41.40098 2.180908 9 57 41.41730 2.172617 10 148 41.37510 2.147933
A.1. Scenário I 88 a.1.5Distances Table 28: Distance between areas/stations di,j Distance di,j Distance di,j Distance di,j Distance d177,192 431.7352 d107,162 1303.422 d192,148 1817.079 d108,148 1542.504 d177,9 1207.32 d107,176 798.5859 d9,108 2004.482 d162,176 701.7969 d177,108 799.2059 d107,84 3082.193 d9,162 830.7663 d162,84 1779.739 d177,162 446.9816 d107,57 3625.005 d9,176 1268.168 d162,57 2591.11 d177,176 375.0533 d107,148 1809.014 d9,84 1257.084 d162,148 2532.482 d177,84 2226.706 d192,9 1612.832 d9,57 1774.846 d7,84 1858.355 d177,57 2904.002 d192,108 411.0985 d9,148 3359.673 d7,57 1439.637 d177,148 2246.887 d192,162 797.4612 d108,162 1202.867 d7,148 3801.518 d107,192 627.2566 d192,176 672.356 d108,176 909.9641 d8,57 1605.997 d107,9 2030.982 d192,84 2529.699 d108,84 2939.563 d8,148 3525.419 d107,108 382.7962 d192,57 3332.652 d108,57 3692.28 d9,148 3359.673 a.1.6Configurations --- config . yml journey: limit:60 #time , in minutes , to rebalance the system velocity:750 #m/min - 45km/h average speed during a trip depot:84 #depot operations: scooters: pickup:1#average time spent on picking up a scooter deliver:1#average time spent on delivering a scooter --- Figure 44: YAML configuration file