More Like this

1. Data-Driven Optimization of Public Transit Schedule

   https://doi.org/10.1007/978-3-030-37188-3_16  

   Basak, Sanchita ; Sun, Fangzhou ; Sengupta, Saptarshi ; Dubey, Abhishek ( January 2019 , Big Data Analytics)

   Bus transit systems are the backbone of public transportation in the United States. An important indicator of the quality of service in such infrastructures is on-time performance at stops, with published transit schedules playing an integral role governing the level of success of the service. However there are relatively few optimization architectures leveraging stochastic search that focus on optimizing bus timetables with the objective of maximizing probability of bus arrivals at timepoints with delays within desired on-time ranges. In addition to this, there is a lack of substantial research considering monthly and seasonal variations of delay patterns integrated with such optimization strategies. To address these, this paper makes the following contributions to the corpus of studies on transit on-time performance optimization: (a) an unsupervised clustering mechanism is presented which groups months with similar seasonal delay patterns, (b) the problem is formulated as a single-objective optimization task and a greedy algorithm, a genetic algorithm (GA) as well as a particle swarm optimization (PSO) algorithm are employed to solve it, (c) a detailed discussion on empirical results comparing the algorithms are provided and sensitivity analysis on hyper-parameters of the heuristics are presented along with execution times, which will help practitioners looking atmore »similar problems. The analyses conducted are insightful in the local context of improving public transit scheduling in the Nashville metro region as well as informative from a global perspective as an elaborate case study which builds upon the growing corpus of empirical studies using nature-inspired approaches to transit schedule optimization« less
2. Optimal algorithms for scheduling under time-of-use tariffs

   https://doi.org/10.1007/s10479-021-04059-3  

   Chen, Lin ; Megow, Nicole ; Rischke, Roman ; Stougie, Leen ; Verschae, José ( September 2021 , Annals of Operations Research)

   Abstract We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-timemore »approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines.« less
3. A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games

   https://doi.org/10.1287/ijoc.2021.1085  

   Contardo, Claudio ; Sefair, Jorge A. ( March 2022 , INFORMS Journal on Computing)

   We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1more »knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.« less
4. IKBT: Solving Symbolic Inverse Kinematics with Behavior Tree

   Zhang, Dianmu ; Hannaford, Blake ( July 2019 , Journal of artificial intelligence research and advances)

   Inverse kinematics solves the problem of how to control robot arm joints to achieve desired end effector positions, which is critical to any robot arm design and implemen- tations of control algorithms. It is a common misunderstanding that closed-form inverse kinematics analysis is solved. Popular software and algorithms, such as gradient descent or any multi-variant equations solving algorithm, claims solving inverse kinematics but only on the numerical level. While the numerical inverse kinematics solutions are rela- tively straightforward to obtain, these methods often fail, due to dependency on specific numerical values, even when the inverse kinematics solutions exist. Therefore, closed-form inverse kinematics analysis is superior, but there is no generalized automated algorithm. Up till now, the high-level logical reasoning involved in solving closed-form inverse kine- matics made it hard to automate, so it’s handled by human experts. We developed IKBT, a knowledge-based intelligent system that can mimic human experts’ behaviors in solving closed-from inverse kinematics using Behavior Tree. Knowledge and rules used by engineers when solving closed-from inverse kinematics are encoded as actions in Behavior Tree. The order of applying these rules is governed by higher level composite nodes, which resembles the logical reasoning process of engineers. It is alsomore »the first time that the dependency of joint variables, an important issue in inverse kinematics analysis, is automatically tracked in graph form. Besides generating closed-form solutions, IKBT also explains its solving strategies in human (engineers) interpretable form. This is a proof-of-concept of using Behavior Trees to solve high-cognitive problems.« less
5. Study on Characteristics of Metric-aware Multipath Algorithms in Real Heterogeneous Networks

   https://doi.org/10.1109/GLOBECOM46510.2021.9685343  

   Zhang, Xiaoya ; Dong, Ping ; Du, Xiaojiang ; Zhang, Yuyang ; Zhang, Hongke ; Guizan, Mohsen ( July 2021 , 2021 IEEE Global Communications Conference (GLOBECOM))

   Multipath transmission is considered one of the promising solutions to improve wireless resource utilization where there are many kinds of heterogeneous networks around. Most scheduling algorithms rely on real-time network metrics, including delay, packet loss, and arrival rates, and achieve satisfying results in simulation or wired environments. However, the implicit premise of a scheduling algorithm may conflict with the characteristics of real heterogeneous wireless networks, which has been ignored before. This paper analyzes the real network metrics of three Chinese heterogeneous wireless networks under different transmission rates. To make the results more convincing, we conduct experiments in various scenarios, including different locations, different times of the day, different numbers of users, and different motion speeds. Further, we verify the suitability of a typical delay-aware multipath scheduling algorithm, Lowest Round Trip Time, in heterogeneous networks based on the actual data measured above. Finally, we conclude the characteristics of heterogeneous wireless networks, which need to be considered in a well-designed multipath scheduling algorithm.