Riccardo Elitropi
558b590810
- Aggiunta classe di calcolo per ottimizzazione ordine delle lavorazioni - Aggiunti vincoli obbligatori e dipendenze suggerite a ShortestPath.
130 lines
5.1 KiB
C++
130 lines
5.1 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2015-2015
|
|
//----------------------------------------------------------------------------
|
|
// File : TwoOpt.cpp Data : 22.12.15 Versione : 1.6l4
|
|
// Contenuto : Miglioramento del percorso spezzandolo in 2 parti e
|
|
// ricollegando con una delle due parti invertite.
|
|
//
|
|
// K Last K Last
|
|
// o o--<- o--o--<-
|
|
// |\/ |
|
|
// |/\ |
|
|
// o o---> o--o--->
|
|
// First K+1 First K+1
|
|
//
|
|
// Modifiche : 22.12.15 DS Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
//--------------------------- Include ----------------------------------------
|
|
#include "stdafx.h"
|
|
#include "ShortestPath.h"
|
|
|
|
// ----------------------------------------------------------------------------
|
|
static void
|
|
SwapNodesForTwoOpt( NODE* pFirst, NODE* pKth, NODE* pLast)
|
|
{
|
|
// inverto il tratto intermedio
|
|
for ( NODE* pCurr = pFirst ; pCurr != pKth ; ) {
|
|
NODE* pSave = pCurr->pNext ;
|
|
pCurr->pNext = pCurr->pPrev ;
|
|
pCurr->pPrev = pSave ;
|
|
pCurr = pSave ;
|
|
}
|
|
// sistemo gli estremi
|
|
pFirst->pNext = pKth->pNext ;
|
|
pKth->pNext->pPrev = pFirst ;
|
|
pKth->pNext = pKth->pPrev ;
|
|
pKth->pPrev = pLast ;
|
|
pLast->pNext = pKth ;
|
|
pFirst = pLast->pNext ;
|
|
pKth = pFirst->pNext ;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
long long unsigned
|
|
ShortestPath::TwoOpt( NODE* pPath)
|
|
{
|
|
const int MAX_TRY = 2048 ;
|
|
unsigned nTry = 1 ;
|
|
unsigned nCount = 1 ;
|
|
NODE* pFirst = pPath ;
|
|
NODE* pFirstDep = m_pCheckDep ;
|
|
do {
|
|
NODE* pLast = pFirst->pPrev ;
|
|
NODE* pKth = pFirst->pNext ;
|
|
NODE* pLastDep = pFirstDep->pPrev ;
|
|
NODE* pKthDep = pFirstDep->pNext ;
|
|
do {
|
|
// se non esistono dipendenze suggerite
|
|
if ( ! ExistSuggDependences()) {
|
|
// lunghezza originale dei tratti da scambiare
|
|
unsigned nEXIST = ArcCost( pLast->nPos, pFirst->nPos) +
|
|
ArcCost( pKth->nPos, pKth->pNext->nPos) ;
|
|
// nuova lunghezza dei tratti da scambiare
|
|
unsigned nTEST = ArcCost( pFirst->nPos, pKth->pNext->nPos) +
|
|
ArcCost( pLast->nPos, pKth->nPos) ;
|
|
// lunghezze originali e nuova del tratto intermedio che viene invertito
|
|
for ( NODE* pCurr = pFirst ; pCurr != pKth ; pCurr = pCurr->pNext) {
|
|
nEXIST += ArcCost( pCurr->nPos, pCurr->pNext->nPos) ;
|
|
nTEST += ArcCost( pCurr->pNext->nPos, pCurr->nPos) ;
|
|
}
|
|
// se lo scambio fa risparmiare
|
|
if ( nTEST < nEXIST) {
|
|
// se non esistono vincoli, effettuo i cambi
|
|
if ( ! ExistConstraints()) {
|
|
SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
|
|
nCount = 0 ;
|
|
}
|
|
// se esistono i vincoli
|
|
else {
|
|
// copio il Path e i puntatori sul Path di test per le dipendenze
|
|
CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
|
|
// effettuo i cambi dei nodi sul path di test per le dipendenze
|
|
SwapNodesForTwoOpt( pFirstDep, pKthDep, pLastDep) ;
|
|
// se il path di test rispetta i vincoli, allora effettuo i cambi sul percorso vero
|
|
if ( IsPathRespectingContraints( m_pCheckDep)) {
|
|
SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
|
|
nCount = 0 ;
|
|
}
|
|
// altrimenti passo al nodo successivo
|
|
else
|
|
pKth = pKth->pNext ;
|
|
}
|
|
}
|
|
// altrimenti passo al nodo successivo
|
|
else
|
|
pKth = pKth->pNext ;
|
|
}
|
|
// se esistono dipendenze suggerite
|
|
else {
|
|
CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
|
|
SwapNodesForTwoOpt( pFirstDep, pKthDep, pLastDep) ;
|
|
if ( IsPathRespectingContraints( m_pCheckDep)) {
|
|
unsigned long long nEXIST = TotalCost( pPath) ;
|
|
unsigned long long nTEST = TotalCost( m_pCheckDep) ;
|
|
if ( nTEST < nEXIST) {
|
|
SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
|
|
nCount = 0 ;
|
|
}
|
|
// altrimenti passo al nodo successivo
|
|
else
|
|
pKth = pKth->pNext ;
|
|
}
|
|
// altrimenti passo al nodo successivo
|
|
else
|
|
pKth = pKth->pNext ;
|
|
}
|
|
} while ( pKth != pLast->pPrev->pPrev && nCount != 0) ;
|
|
if ( nCount != 0)
|
|
pFirst = pFirst->pNext ;
|
|
nCount ++ ;
|
|
nTry ++ ;
|
|
} while ( nCount < m_nNumPnts && nTry < MAX_TRY) ;
|
|
|
|
// ricalcolo il costo del percorso
|
|
return TotalCost( pPath) ;
|
|
}
|
|
|