Abstract
In this paper, we investigate a general algorithm for converting the 0–1 integer linear programming problem (0-1IP) into an optimal transition firing sequence problem (OFSP) of a Petri net (PN). The general 0-1IP can be visualized graphically and then analyzed using the PN theory after application of our proposed conversion algorithm. The proposed algorithm is applied to a traveling salesman problem, a vehicle routing problem and an automated guided vehicles (AGV) routing problem. A PN reduction technique is employed to reduce the size of the PN. Valid inequalities are derived using reachability analysis of the converted PN model. These inequalities are imposed on the original 0-1IP. Computational results show that the total computational time for solving an AGVRP with the valid inequalities derived using the reachability analysis is significantly reduced.
| Original language | English |
|---|---|
| Pages (from-to) | 157-172 |
| Number of pages | 16 |
| Journal | Information Sciences |
| Volume | 400-401 |
| DOIs | |
| Publication status | Published - Aug 1 2017 |
| Externally published | Yes |
Keywords
- 0–1 integer linear programming problem
- AGV systems
- Discrete event systems
- Optimal transition firing sequence problems
- Petri net
- Reachability analysis
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence