CYCLIC ROUTING

RESEARCH TO DATE RELATED TO VEHICLE ROUTING HAS ASSUMED THATTHE CUSTOMER WILL ONLY BE VISITED ONCE IN THE TIME PERIOD UNDER CONSIDERATION. USING THIS ASSUMPTION THE PROBLEMS ARETO ASSIGN EACH CUSTOMER TO A ROUTE, SEQUENCE THE ROUTE, AND SCHEDULE THE VISIT TO EACH CUSTOMER CONSISTENT WITH THE ROUTE. FOR A LARGE CLASS OF PRACTICAL VEHICLE ROUTING PROBLEMS, THE ONE TIME PERIOD ASSUMPTION IS NOT ADEQUATE BECAUSE CUSTOMERS MUST BE VISITED AT REGULAR INTERVALS (E.G., ONCE A WEEK, TWICE A WEEK, ETC.). WHAT DISTINGUISHESTHIS CLASS OF PROBLEMS FROM THE MORE COMMONLY ADDRESSED ROUTING PROBLEMS IS THIS REQUIREMENT FOR PERIODIC VISITS. SUCH PROBLEMS WILL BE REFERRED TO AS "CYCLIC ROUTING" PROBLEMS WHERE THE CYCLE IS THE LENGTH OF TIME BEFORE THE ROUTING PATTERN REPEATS. RESEARCH IS PROPOSED TO DEVELOP AND TEST METHODOLOGIES AND ALGORITHMS TO ADDRESS PROBLEMS OFCYCLIC ROUTING. TASKS OUTLINED IN THIS PROPOSAL ISOLATE THESPECIAL PROPERTIES OF CYCLIC ROUTES, DEVELOP METHODOLOGICAL APPROACHES FOR IMPORTANT SUBCLASSES, PRODUCE PROTOTYPES OF ALGORITHMS, TEST THESE PROTOTYPES WITH TEST DATA SETS, AND SELECT PROMISING APPROACHES FOR FURTHER DEVELOPMENT. SINCE MUCH OF REAL-WORLD ROUTING FALLS IN THE CATEGORY OF CYCLIC ROUTING SYSTEMS, SUCCESSFUL COMPLETION OF THE RESEARCH WILL YIELD TOOLS AND TECHNIQUES WITH HIGH COMMERCIAL VALUE.