An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints

Koskosidis, Yiannis A.; Powell, Warren B.; Solomon, Marius M.
May 1992
Transportation Science;May92, Vol. 26 Issue 2, p69
Academic Journal
This article focuses on a study that describes an optimization-based heuristic for vehicle routing and scheduling with soft time window constraints in traffic. The problem of vehicle routing (VRP) with time window constraints arises in a variety of applications, including retail distribution, mail and newspaper delivery, municipal waste collection, fuel oil delivery, school bus routing, airline and railroad scheduling, trucking and bargeline fleet scheduling, demand responsive bus systems, and more. The article discusses a new methodological approach for the time constrained VRP, based on the generalized assignment heuristic proposed by researchers M. Fisher and R. Jaikumar. A significant change from the original generalized assignment heuristic is its iterative application where approximate clustering costs are successively improved. Loose capacity constraints are very desirable for local insertion and improvement heuristics, since they allow more flexibility to perform local operations, such as insertion of a customer in an existing tour or pair-wise switches between tours.


Related Articles

  • Modelling Resource-constrained Project Scheduling Problem and its Solution by Genetic Algorithm. Chunlai Chai // Journal of Digital Information Management;Apr2013, Vol. 11 Issue 2, p87 

    The optimization of the resource-constrained project scheduling is an NP-hard problem. Complexity of the algorithm for solving this problem increases exponentially with the increase of resource constraints. Therefore, traditional optimization methods based on Excel tables cannot calculate the...

  • Genetic Algorithm for Flexible Job Shop Scheduling Problem - a Case Study. Guevara, Gabriela; Pereira, Ana I.; Ferreira, Adriano; Barbosa, José; Leitão, Paulo // AIP Conference Proceedings;2015, Vol. 1648 Issue 1, p1 

    This paper proposes the impact assessment of the workers in the optimal time of operations in a Flexible Job Shop Scheduling Problem. In this work, a real enterprise was studied. The problem consists in finding the workers operations schedule, taking into account the precedence constraints. The...

  • A generic framework for constraint-directed search and scheduling. Beck, J. Christopher; Fox, Mark S. // AI Magazine;Winter98, Vol. 19 Issue 4, p101 

    Presents a generic framework for constraint-directed search and scheduling. Conceptualization of a number of algorithms from the constraint-directed-scheduling research within the framework; Prospects for an overall comparison of scheduling strategies.

  • NEW NUMERICAL ALGORITHMS FOR MINIMIZATION OF NONLINEAR FUNCTIONS. Karthikeyan, K.; Khadar Babu, S. K.; Rajesh Anand, B. // International Journal on Computer Science & Engineering;2011, Vol. 3 Issue 1, p69 

    In this paper, we propose few new algorithms of third order convergence for minimization of nonlinear functions which is based on geometric construction of iteration functions of order three to develop cubically convergent iterative methods. Then comparative study among the new algorithms and...

  • Self-Triggered Model Predictive Control Using Optimization with Prediction Horizon One. Kobayashi, Koichi; Hiraishi, Kunihiko // Mathematical Problems in Engineering;2013, p1 

    Self-triggered control is a controlmethod that the control input and the sampling period are computed simultaneously in sampleddata control systems and is extensively studied in the field of control theory of networked systems and cyber-physical systems. In this paper, a new approach for...

  • Constrained derivative-free optimization on thin domains. Martínez, J.; Sobral, F. // Journal of Global Optimization;Jul2013, Vol. 56 Issue 3, p1217 

    Many derivative-free methods for constrained problems are not efficient for minimizing functions on 'thin' domains. Other algorithms, like those based on Augmented Lagrangians, deal with thin constraints using penalty-like strategies. When the constraints are computationally inexpensive but...

  • Local Geometrically Enriched Mixtures for Stable and Robust Human Tracking in Detecting Falls. Kokkinos, Michalis; Doulamis, Nikolaos D.; Doulamis, Anastasios D. // International Journal of Advanced Robotic Systems;Jan2013, Vol. 10, p1 

    Detecting a fall through visual cues is emerging as a hot research agenda for improving the independence of the elderly. However, the traditional motion-based algorithms are very sensitive to noise, reducing fall detection accuracy. Another approach is to efficiently localize and then track the...

  • An Improved RANSAC Algorithm based on the Geometric Constraints. Fei Hui; Ke-nan Mu; Xiang-mo Zha; Jun-yan Ma // AIP Conference Proceedings;2014, Vol. 1618, p420 

    Eliminating false matching is an important part in image stitching technology. Traditional eliminating erroneous matching method in the field of image stitching is RANSAC algorithm, but this method need numerous iterations and complex computation, and it often could not completely eliminate the...

  • On the chaotic behavior of the primal-dual affine-scaling algorithm for linear optimization. Bruin, H.; Fokkink, R.; Gu, G.; Roos, C. // Chaos;Dec2014, Vol. 24 Issue 4, p1 

    We study a one-parameter family of quadratic maps, which serves as a template for interior point methods. It is known that such methods can exhibit chaotic behavior, but this has been verified only for particular linear optimization problems. Our results indicate that this chaotic behavior is...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics