A heuristic algorithm for the stochastic vehicle routing problems with soft time windows

Abstract

In this paper, a very complicated class of Vehicle Routing Problem (VRP), Stochastic Vehicle Routing Problem with Soft Time Windows (SVRPSTW), is studied. In this kind of problem the customer demand and the presence of the customer are assumed to uncertain. And each customer is bounded by a service time window but lateness arrival at the customer is allowed by a penalty added into the total cost. The service vehicle returns to the depot whenever its capacity is attained or exceeded, and resumes its collections along the planned route. After describing the concept of SVRPSTW, a mathematical programming formulation is developed in order to study the effects of the stochastic demands and customers on transportation. A genetic based algorithm is proposed for this intractable problem in order to obtain optimal or near optimal solutions that have minimum total cost. Computational examples on a group of instances are given, showing the proposed approach is a simple but effective ways to solve such problems.