Knowledge Representation For The Model Of Vehicle Routing Problems With Time Windows

Aiming at overcoming deficiencies in the conventional process of modeling and solving Vehicle Routing Problem with Time Windows (VRPTW), this paper focuses on the knowledge-based model representation for VRPTW. Problem's known knowledge, modeling knowledge and solution knowledge are integrated and represented as model's entire knowledge by introducing theories and methods of Artificial Intelligence (AI) and Knowledge Engineering (KE) into model representation. The main researches of this work are as follows.(1)We deeply analyze the characteristics of the mathematical model and existing efficient heuristic algorithms for VRPTW, and examine achievements made in the field of model representation, which set foundations for the following representation method;(2) Principles of the proposed knowledge representation for the model of VRPTW are indicated on the basis of analysis of the problem knowledge, modeling knowledge of experts, and solution knowledge, and an integrated knowledge architecture for the model is presented;(3) According to the indicated principles of the representation and assisted by existing databases for VRPTW, we present a six-component knowledge representation for the model of VRPTW in a computer. The six components are B, R, G, I, S, C. The representation method unifies data, facts, rules, methods and reasoning processes needed when solving VRPTW;(4) Based on the presented model representation method, we solve the gas distribution vehicle routing problem with time windows in the north area of Dalian Distribution Center of China Petroleum Corp.The proposed model representation for VRPTW eliminates the dependence on experts in the processes of modeling and problem-solving. The concept of unifying all knowledge simplifies the structure of routing system and improves the consistency of solution processes in the system. And the contents of the six components can be easily adjusted according to different vehicle routing problems, thereby enhancing the dynamic and adaptive capabilities of modeling and problem-solving processes of Vehicle Routing Problem.